16
$\begingroup$

Is NP in $DTIME(n^{poly\log n})$?

$\endgroup$
22
$\begingroup$

$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$.

$\endgroup$
1
  • 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$
    – Matt Groff
    Mar 17 '14 at 2:00
21
$\begingroup$

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

$\endgroup$
4
  • 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$ Mar 21 '14 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$ Mar 21 '14 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$ Mar 21 '14 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$ Mar 21 '14 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy