New answers tagged complexity-theory
1
You can use Clarkson's algorithm to find the smallest (non-degenerate) enclosing triangle in $O(d\log^2 n)$ expected time, where $d$ is the dimension of your input. So, for constant dimensions, it takes $O(\log^2 n)$ expected time. The algorithms is applicable, because the smallest triangle problem is an LP-type problem.
Clarkson's algorithm has many ...
0
Usually, mathematical definitions are not computational. Informally, mathematics describes the "what", not "how" you compute it.
However, for some problems there is an obvious algorithm deciding them. I would not see an issue with a sentence like this:
The problem $\{x \in \mathbb N\,|\, x < c\}$ can be decided in $O(n)$ for all ...
0
To solve such a problem, you should have more of a "programming" point of view rather than a "Turing machine" point of view.
Sure, $\mathsf{NP}$ is defined considering the executing time of a Turing machine, however we, human beings, are not made to think in TM. You could think of it as the same difference between programming in a very ...
3
The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ and $V'$ forms a complete graph. Also, there are no edges between $V$ and $V'$. Let the new graph be $G' = (V' \cup V, E')$ which is also a hard instance. And, $|...
1
It is known that $BQP \subseteq PSPACE \subseteq EXP \subseteq NEXPTIME$.
If $BQP = NEXPTIME$ then $PSPACE = EXP $ and $ EXP = NEXPTIME $.
This would imply $L = P$ and $P = NP$.
3
Yes. For instance, define $f$ so that $f(x)=1$ if $x$ is an encoding of a 3-colorable graph, or $f(x)=0$ otherwise. Since 3-coloring is NP-hard, it is NP-hard to compute $f$. (If you could compute $f$ efficiently, you could solve 3-coloring efficiently.)
2
Miltersen, Radhakrishnan and Wegener construct, in their paper On converting CNF to DNF, a function which has a polynomial size CNF, but whose smallest DNF has size $2^{n-\Theta(n/\log n)}$.
In particular, even if the input CNF has polynomial size, you cannot expect to do better than exponential time, since the output might be that long.
1
The magic of mathematical definitions is that they provide a complete specification of a concept. You don't need to know anything other than the definition.
A language over an alphabet $\Sigma$ is an arbitrary collection of strings over $\Sigma$. In complexity theory, we usually assume that $\Sigma = \{0,1\}$. A circuit family is a sequence of circuits $\...
1
The relationship is that a short SOP expression implies a low Kolmogorov complexity, but not vice versa. If you have a short SOP expression, then that is a concise way to compress the string, hence Kolmogorov complexity is low. However, there might be strings that can be compressed in another way even though the SOP expression is long, and those strings ...
5
One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}_{ij} = x_i x_j$ (the vectors have length $k^2)$.
We have
$$
\langle \hat{x}, \hat{y} \rangle =
\sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2.
$$
Therefore if you know the minimum inner product, you can solve OV. It remains to ...
2
We can analyze the number of arithmetic operations as a function of $n$. Let us call the algorithms O (for "original"), A (for "speedup A") and B (for "speedup B").
Let us denote by $f_X(n)$ the number of additions performed by algorithm X. We have that
$f_O(n) = 1 + 3n$,
$f_A(n) = 0 + 3n$, and
$f_B(n) = 1 + 2n$.
So the only ...
2
Assuming that $NP\not= PSPACE$ and $PSPACE \not= EXPTIME$, all
$PSPACE$-complete problems are incomplete in $EXPTIME$
1
The answer depends on the coding of $n$.
The set $\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n
\text{ tape space } \}$ is $PSPACE$-complete. But the set $\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n
\text{ tape space } \}$ where $n$ is binary coded is $EXPSPACE$-complete.
2
If the Polynomial Hierachy does not collapse then there are incomplete sets between $PH$ and $PSPACE$, see https://cstheory.stackexchange.com/questions/7639/is-there-a-pspace-intermediate-language/7640. These sets would be also incomplete in $EXP$, because $PSPACE \subseteq EXP$
0
If you have a proof that $(P=NP)\Leftrightarrow (P\not= NP) $
then $P=NP$ is proveable is equivalent to $P\not= NP$ is provable.
This would mean that neither $P=NP$ nor $P\not= NP$ is provable.
But if there would be a proof, that $P=NP$ is not provable then
it would be proven that one cannot find an efficient algorithm for SAT
or any other $NP$-complete ...
1
If P=NP implies P≠NP, then P≠NP (unconditionally).
Similarly, if P≠NP implies P=NP, then P=NP.
If both are true, then both P≠NP and P=NP, and so the axioms of mathematics are inconsistent. Most (but not all) mathematicians consider this quite unlikely.
3
Any BQP-complete problem should suffice, since BQP is contained in EXPTIME but not believed to be contained in NP and not believed to be equal to EXPTIME.
3
Any $\mathsf{NP}$-complete problem is in $\mathsf{EXPTIME}$ and not known to be $\mathsf{EXPTIME}$-complete, since it is still unknown whether $\mathsf{NP} = \mathsf{EXPTIME}$ or not.
0
NP is not the subset of co-NP unless we assume A be an NP-Complete problem and A∈ co-NP (which is not possible) then we can say all NP problems are a subset of co-NP problems since we can reduce all NP problems to problem A which is NP-complete it follows that for every problem in NP, we can construct a non-deterministic Turing machine that decides its ...
1
The answer depends on the class $C$. Many classes will be closed under your operation, but some are not. For example, DCFL, the class of all deterministic context-free language, is not. To show this, we slightly adapt the counterexample in this answer. Define
$$
L_A = \{ a^i b^j c^k : i \neq j \}; L_B = \{ a^i b^j c^k : j \neq k \}; L_1 = \{ ,w : w \in L_A \}...
1
Since $\Sigma^{P}_2 \subseteq PH \subseteq PSPACE$, then showing this will prove that $PH=PSPACE$, showing, for
example, this important implication.
In addition, another immediate but important implication is that the polynomial hirarchy collapses to $\Sigma^P_2$ - which shows that there is no gain in "strength" by adding more alternations above ...
0
Suppose $f\in \Theta(g)$ and $h\notin \mathcal{O}(g)$. That means:
$$\exists A>0, B>0, \forall n\geqslant 0, Ag(n) \leqslant f(n) \leqslant Bg(n)$$
and
$$\forall C>0, \exists n\geqslant 0, h(n) > Cg(n)$$
Therefore, for all $C>0$, there exists $n\geqslant 0$ such that $h(n) > (C-A)g(n)$. We conclude that $f(n) + h(n) > Ag(n) + (C-A)g(n) = ...
1
If H(x,x) goes into an infinite loop, then that fact already proves that H does not solve the halting problem. If H solves the halting problem, then it never goes into an infinite loop.
If we are trying to figure out whether it's possible to solve the halting problem, we can ignore all the functions that sometimes enter infinite loops. They obviously don't ...
11
However, if P != NP then both NP and coNP are in exptime and not better.
This is not neccesarily true. It just means that some NP (and coNP) problems cannot be solved in polynomial time. This is not necessarily the same as requiring exponential time (e.g. $n^{\log n}$ is not polynomial but also not exponential).
If P != NP then it makes sense that NP = ...
4
We know that $\mathsf{P} \subseteq \mathsf{NP}$ and that $\mathsf{P}^{\mathsf{NP}} \subseteq \mathsf{NP}^{\mathsf{NP}}$; this follows directly from the definitions.
More interesting are the two reverse inclusions, $\mathsf{NP} \subseteq \mathsf{P}$ and $\mathsf{NP^{NP}} \subseteq \mathsf{P^{NP}}$. The former implies the latter: indeed, if $\mathsf{NP} \...
32
No such problem is known (not with a known mathematical proof of a lower bound). Of course cryptographers would jump on it if we had one. As a result, cryptography is currently based on assumptions that we hope are true but we cannot prove (these are sometimes called "hardness assumptions"), and then we prove that if the assumption is valid, then ...
0
A mapping $f$ from instances of a decision problem $A$ to instances of a decision problem $B$ is a reduction if $x \in A$ iff $f(x) \in B$.
In your case, instances of both problems are of the form $(G,k)$. Such instances are Yes instances if there is a clique-cover of $G$ of size at most $k$.
Thus a function mapping $(G,k)$ to $(G',k')$ is a reduction ...
Top 50 recent answers are included