I have a certain impossibility result that holds unless $\mathsf{NP} = \mathsf{QP}$. It seems quite likely that one could strengthen this to hold unless $\mathsf{NP} = \mathsf{P}$, which I would not need to motivate further in my paper.

Unfortunately, I don't have time to do that in this particular paper, so instead want to quickly motivate to cryptographers why $\mathsf{NP} = \mathsf{QP}$ is unlikely. I know of basic consequences (namely that it would badly violate essentially any form of ETH, so would imply that tournament dominating set is in P), but not much else.

Of course, there's also the obvious motivation that $\mathsf{NP} = \mathsf{QP}$ implies $\mathsf{NP}\cap\mathsf{coNP}\subseteq \mathsf{QP}$. Most hardness assumptions used in crypto are in $\mathsf{NP}\cap\mathsf{coNP}$, and a particular weak hardness assumption (fixed characteristic finite field discrete log) is known to be in $\mathsf{QP}$. One can therefore interpret $\mathsf{NP} = \mathsf{QP}$ as "most hardness assumptions in crypto are roughly comperable to fixed characteristic finite-field discrete log", which may work fine as motivation.

Still, is there any clearer motivation from a complexity theory point of view? For example a hierarchy collapse/something along those lines.

  • 2
    $\begingroup$ Violates ETH. Related: no known NP-complete problems are known to have subexp time complexity. $\endgroup$ Commented Oct 1, 2020 at 2:07
  • 5
    $\begingroup$ If QP is quasipolynomial time, then it is unequal to NP unconditionally: QP is closed under quasipolynomial-time reductions, whereas by a padding argument, the closure of NP under quasipolynomial-time reductions is NQP (nondeterministic quasipolynomial time), which is different from NP by the nondeterministic time-hierarchy theorem. $\endgroup$ Commented Oct 1, 2020 at 5:23
  • 1
    $\begingroup$ See also cstheory.stackexchange.com/questions/21571 for a related question about the inclusion $\mathrm{NP\subseteq QP}$ (without any exciting answers, I would say). $\endgroup$ Commented Oct 1, 2020 at 6:17
  • 1
    $\begingroup$ @EmilJeřábek I think that argument + the reference to the $\mathsf{NP}\subseteq \mathsf{QP}$ question is likely a definitive answer to this question. If you want to write it up as an answer I'll accept it. $\endgroup$ Commented Oct 1, 2020 at 15:22
  • $\begingroup$ I have work on the problem P vs NP, I would like to discuss it, if interested answer this message. $\endgroup$ Commented Nov 1, 2020 at 21:59

1 Answer 1


We can prove $\mathrm{NP\ne QP}$ unconditionally: $\mathrm{QP}$ is closed under quasipolynomial-time reductions, whereas $\mathrm{NP}$ is not (a simple padding argument shows that the closure of $\mathrm{NP}$ under quasipolynomial-time reductions includes all languages computable in nondeterministic quasipolynomial time, and this class strictly contains $\mathrm{NP}$ by the nondeterministic time-hierarchy theorem).

As for consequences of the weaker assumption $\mathrm{NP\subseteq QP}$, see the question Is NP in $DTIME(n^{poly\log n})$?.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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