All Questions
1,809 questions
2
votes
2
answers
390
views
Oracle Separation Survey
Is there a survey (or a website) somewhere that lists all known separation results?
I.e. it has a list of triples:
$$ (C_1, C_2, A)$$
where
...
- 21
2
votes
1
answer
1k
views
Does P≠NP over ℝ imply P≠NP ?
Does P≠NP over ℝ imply P≠NP ?
where ℝ is for Real number algorithms as described by Smale with a suitable formulation of P≠NP over ℝ.
Complexity Theory and Numerical Analysis, Steve Smale, 2000
...
- 89
2
votes
2
answers
640
views
Sorting a binary matrix diagonal in polynomial time while preserving rows
Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given ...
- 121
2
votes
1
answer
171
views
On roots of irreducible quadratics modulo composites
Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?
- 13.9k
2
votes
1
answer
180
views
Intersection of a $\mathbb{Q}$-affine space with $\mathbb{Z}^n$
Let $E$, a $\mathbb{Q}$-affine space of arbitrary dimension included in $\mathbb{Q}^n$. Is it possible to check efficiently if $E \cap \mathbb{Z}^n$ is empty or not?
If is an hard problem could give ...
- 215
2
votes
1
answer
406
views
Are there any efficient (polynomial time) algorithms for finding if a multivariate quadratic polynomial has a root?
I know that in general, polynomial satisfiability is NP; however, I'm curious to know what work has been done on special classes of polynomials, and in particular quadratic polynomials of multiple ...
- 173
2
votes
2
answers
4k
views
Greedy approach to 0-1 Knapsack problem in specific instances
The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
- 949
2
votes
1
answer
857
views
What is the relationship between singular value decomposition and solving linear systems?
It is known that solving systems of linear equations is reducible to SVD in a straightforward way; if you want to solve $\mathbf{Ax}=\mathbf{b}$, then you can perform SVD on $\mathbf{A}$ and minimize $...
- 2,019
2
votes
1
answer
539
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...
- 13.9k
2
votes
1
answer
500
views
What is the big-O time complexity of computing $1/N$ to $\log_{2}(N)$ bits of precision?
I am considering large integer values of $N$ (100 or more digits in base-$10$).
In my algorithm, I need to be able to compute the reciprocal of $N$ with enough precision that the repetend will have ...
- 99
2
votes
1
answer
182
views
Complexity of set-partition problems
given a universe $\mathcal{U}$ of elements and a system $\mathcal{S}$ of weighted subsets of $\mathcal{U}$ whose union covers $\mathcal{U}$.
Assuming the existence of at least one subsytem $S\...
- 13.2k
2
votes
1
answer
415
views
How hard is it to compute these prime factor related problems?
We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).
Let $\omega(n)$ be number of distinct ...
- 13.9k
2
votes
1
answer
364
views
What is known about space and time complexity of division and base change?
The paper ON THE RAPID COMPUTATION OF VARIOUS POLYLOGARITHMIC CONSTANTS by Bailey, Borwein, and Plouffe gives sophisticated calculations which I will not summarize. But they remark
We are ...
- 11.1k
2
votes
1
answer
1k
views
Complexity of a variant of Four coloring theorem
The Four color theorem states that every planar graph can be properly colored by four colors. An equivalent statement is that every bridgeless planar cubic graph is 3-edge colorable. Therefore, 4-...
- 2,993
2
votes
3
answers
1k
views
Quadratic Programming With Piecewise Linear Term
The problem I have can be defined as:
$$
\min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}
$$
s.t. linear equality constraints:
$$
\mathbf{Ax=b}
$$
and linear inequality ...
- 131
2
votes
2
answers
450
views
How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT?
I am interested in the complexity of the following problem:
GENERAL-SQUARE-PRODUCT
INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a ...
- 161
2
votes
1
answer
1k
views
Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?
Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...
- 241
2
votes
3
answers
2k
views
Efficient Algorithm For Projection Onto A Convex Set
Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:
$\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2
\;\;
\...
2
votes
2
answers
418
views
Lovasz theta function - uses
Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
2
votes
2
answers
837
views
Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph
Hi everyone!
This is my first post, apologies if I made any mistakes anywhere.
Here goes the question:
Consider all length 7 binary sequences.
Let $X$ be the set of sequences with hamming weight 3 ...
- 360
2
votes
4
answers
2k
views
Efficient algorithm for finding the minima of a piecewise linear function
Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:...
- 823
2
votes
1
answer
534
views
Is there an interactive proof system for factoring with the perfect zero knowledge property?
Given the decision version of the factoring problem, is there an interactive proof system with the perfect zero knowledge property? I know there is for just the zero knowledge property, but is there ...
2
votes
1
answer
125
views
The counterpart of productive set with polynomial computational complexity
For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...
- 3,094
2
votes
1
answer
158
views
On sets of rectangles that can all together form at least one big rectangle
Let us say a set of $n$ rectangles is rectifiable if all $n$ rectangles together form a big rectangle without gaps or overlaps.
Question: How hard computationally is the question of deciding whether a ...
- 5,979
2
votes
1
answer
116
views
Family of PTIME sets where it is hard to name elements
Call a function$$\mathbb{N}\times \mathbb{N}\to \{0, 1\}, \quad (n, m)\to f(n, m)$$computable in polynomial time in $\log n+\log m$ a PTIME family.
Given a PTIME family $f$ call a computable function $...
user409739
2
votes
2
answers
422
views
Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
- 461
2
votes
1
answer
101
views
The complexity of sorting a list having one free cell
Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say ...
- 42k
2
votes
1
answer
340
views
Bit complexity of Barvinok's algorithm
I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.
What exactly is this arithmetic complexity?
...
- 13.9k
2
votes
1
answer
1k
views
What does the basis of the null space of the constraint matrix of a flow problem look like?
Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form:
$$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$
...
- 31
2
votes
1
answer
183
views
Graph classes where finding explicit coloring have certificate that it is minumum
Graph coloring doesn't have certificate that smaller coloring doesn't exist in general.
I am looking for graph classes where finding explicit coloring is not polynomial and have polynomially ...
- 25.4k
2
votes
2
answers
219
views
Boundedness of ratio of linear functions
Consider the function
\begin{eqnarray}
f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i},
\end{eqnarray}
over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
- 23
2
votes
2
answers
166
views
Size-limited oracles
I am interested in complexity of algorithms which have access to the following peculiar sort of oracle:
Suppose that an invocation of an algorithm f with an input of size n has access to an oracle ...
2
votes
1
answer
369
views
Maximizing positive definite quadratic using the eigendecompoisition
Consider the problem:
$\textrm{max}\;\; x^T Q x$
subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix.
I believe this problem is NP-hard (although I have only found hardness ...
- 53
2
votes
1
answer
153
views
Structure of class P
Hi all,
1. Has there been any work done on trying to distinguish between different Polynomial Time Hierarchies say, O(n) vs O(n^2) problem? May be Turing Machine is too general for that. May be the ...
- 151
2
votes
2
answers
687
views
Could this be a NP complete?
Given a undirected and unweighted graph G(V,E). M is a subset of vertices of V.
s is a vertex in V - M.
Find an optimal tree T of G defined as:
(1) M and s are in V(T)
(2) Distance (which is ...
- 131
2
votes
1
answer
305
views
existence of l1 embedding using LP feasibility
hello
Let (A, d) be an n-point metric space
for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t.
$\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t*...
- 239
2
votes
1
answer
1k
views
Linear Programming Cost Function [closed]
I need to add the following to my LP problem:
If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2.
Example: if 30 workers are hired in ...
2
votes
4
answers
2k
views
Is there any space(n) complete language?
Does space(n) have a complete language? Actually the following was in a complexity cource final exam :
if A is SPACE(n) hard then A is also PSPACE-hard
(this is supposed to be shown by padding...i ...
- 21
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
2
votes
1
answer
232
views
On the computational complexity of Pepin's test
Let $F_{n} = 2^{2^{n}} + 1$, where $n > 0$.
Pepin's Test asserts that $F_{n}$ is prime if and only if $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.
QUESTION: What is the big-$\mathcal O$ complexity of ...
- 99
2
votes
1
answer
485
views
Odd cycle transversal
Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...
2
votes
1
answer
871
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1
answer
237
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
2
votes
1
answer
143
views
Expressing a torsion point of an elliptic curve as a combination of the generators
I'm facing the following problem:
Suppose that we have a finite field $\mathbb{F}_p$ and an elliptic curve $E$ defined over it. Suppose that for $m\in \mathbb{Z}$ not multiple of the characteristic of ...
- 297
2
votes
1
answer
243
views
Does quantifier elimination help here?
Suppose we have a quantified linear program
$$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$
$$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$
$$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$
$$...
- 1,826
2
votes
1
answer
159
views
Counting lattice points can some give all?
Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\...
- 13.9k
2
votes
1
answer
240
views
valuation from $\mathbb{Z}^n$ into $\mathbb{Z}$. Easy way?
Let $\mathcal{F}:=\{f_a\}_{a\in\mathbb{Z}}$ be a set of symbols indexed by the integers and satisfying the rules:
$$f_a=f_{-a} \qquad \text{and} \qquad f_af_b=f_{a+b}+f_{a-b}.$$
Define a linear ...
- 43.2k
2
votes
1
answer
220
views
Bounded Arithmetic and Counting
Let $\mathcal{L}=\{0,S,+,\cdot,=,<,X,R,S\}$ be the language of arithmetic with three additional predicate symbols $X(v)$, $R(v,u)$ and $S(v,u)$.
Let $\phi(x),\psi(x,y)$ and $\eta(x,y)$ be formulas ...
- 1,689
2
votes
2
answers
438
views
Perturbation of Linear Programs
Consider the linear program,
$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\
& x \geq 0\end{array}$$
I want to study the sensitivity of the optimal $x^*$ ...
- 275
2
votes
1
answer
93
views
Directed edge-colouring
I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.
Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...
- 903