Is NP in $DTIME(n^{poly\log n})$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
$DTIME(n^{polylogn})$ is known as $QP$ (quasi-polynomial).
It is widely believed that $NP\not \subset QP$, although it is a stronger statement than $P\neq NP$.
Some common conjectures, such as the Exponential Time Hypothesis imply $NP\not \subset QP$.
-
6$\begingroup$ You say that "Some common conjectures...". What are the others besides ETH? I'm extremely interested because I'm currently working on relating NP and QP - at least I hope so... $\endgroup$ Commented Mar 17, 2014 at 2:00
$\begingroup$
$\endgroup$
4
Another good reason to believe $NP\not\subseteq QP$ is that $NP\subseteq QP$ implies $EXP=NEXP$, and the latter is thought highly unlikely. This implication can be proved by a padding argument, see, e.g., in the proof of Proposition 2 in the following paper:
H. Buhrman and S. Homer, "Superpolynomial circuits, almost sparse oracles and the exponential hierarchy," Foundations of Software Technology and Theoretical Computer Science, Springer LNCS Vol. 652, 1992, pp. 116-127, pdf
-
8$\begingroup$ I like this answer a lot. Given R B's answer, it makes me wonder what, if any, is the relationship between ETH and the assumption $\mathsf{EXP} \neq \mathsf{NEXP}$. $\endgroup$ Commented Mar 21, 2014 at 15:27
-
1$\begingroup$ @Joshua I did not search the literature about this, but, I think, any violation of ETH probably implies some collapse at a higher level. I guess, the level depends on "how strongly" the ETH is violated, stronger violations yielding more dramatic collapses. As pointed out in the answer, the strong ETH violation of $NP\subseteq QP$ implies $EXP=NEXP$. If we take a milder violation, such as assuming that $NP$ is in a subexponential class larger than $QP$, then the collapse is probably shifted upwards (e.g., to double exponential classes or even higher). $\endgroup$ Commented Mar 21, 2014 at 16:11
-
2$\begingroup$ Thansk, but I was asking about a direct implication either way between ETH and $\mathsf{EXP} \neq \mathsf{NEXP}$. We now have two answers - ETH implies $\mathsf{NP} \not\subseteq \mathsf{QP}$ and $\mathsf{NEXP} \neq \mathsf{EXP}$ implies $\mathsf{NP} \not\subseteq \mathsf{QP}$ - and I was curious if one was a consequence of the other. $\endgroup$ Commented Mar 21, 2014 at 16:16
-
2$\begingroup$ Unfortunately, I am not aware of a direct implication. On another note, it is quite interesting that ETH violations can yield not only collapses, but also separations, in terms of circuit lower bounds. A paper of Ryan Williams (pdf) proves that even the slightest ETH violation would imply certain notoriously hard to prove circuit lower bounds. $\endgroup$ Commented Mar 21, 2014 at 19:17