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$
  • 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
19
$\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$
  • 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$ – Joshua Grochow 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$ – Andras Farago 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$ – Joshua Grochow 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$ – Andras Farago 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.