9
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Violates ETH. Related: no known NP-complete problems are known to have subexp time complexity. $\endgroup$ – Joshua Grochow Oct 1 '20 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$ – Emil Jeřábek Oct 1 '20 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$ – Emil Jeřábek Oct 1 '20 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$ – Mark Oct 1 '20 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$ – Vinicius Ricardo Nov 1 '20 at 21:59
18
$\begingroup$

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})$?.

$\endgroup$

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.