<p>We can prove <span class="math-container">$\mathrm{NP\ne QP}$</span> unconditionally: <span class="math-container">$\mathrm{QP}$</span> is closed under quasipolynomial-time reductions, whereas <span class="math-container">$\mathrm{NP}$</span> is not (a simple padding argument shows that the closure of <span class="math-container">$\mathrm{NP}$</span> under quasipolynomial-time reductions includes all languages computable in nondeterministic quasipolynomial time, and this class strictly contains <span class="math-container">$\mathrm{NP}$</span> by the nondeterministic time-hierarchy theorem).</p>
<p>As for consequences of the weaker assumption <span class="math-container">$\mathrm{NP\subseteq QP}$</span>, see the question <a href="https://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n">Is NP in $DTIME(n^{poly\log n})$?</a>.</p>

CC BY-SA 4.0
2020-10-01T19:57:45.213Z
2020-10-01T19:57:45.213Z
Emil Jeřábek
<p>I have a certain impossibility result that holds unless <span class="math-container">$\mathsf{NP} = \mathsf{QP}$</span>. It seems quite likely that one could strengthen this to hold unless <span class="math-container">$\mathsf{NP} = \mathsf{P}$</span>, which I would not need to motivate further in my paper.</p>
<p>Unfortunately, I don't have time to do that in this particular paper, so instead want to quickly motivate to cryptographers why <span class="math-container">$\mathsf{NP} = \mathsf{QP}$</span> is unlikely. I know of basic consequences (namely that it would badly violate essentially any form of ETH, so would imply that <a href="https://cstheory.stackexchange.com/questions/38473/implication-of-exponential-time-hypothesis-falseness">tournament dominating set is in P</a>), but not much else.</p>
<p>Of course, there's also the obvious motivation that <span class="math-container">$\mathsf{NP} = \mathsf{QP}$</span> implies <span class="math-container">$\mathsf{NP}\cap\mathsf{coNP}\subseteq \mathsf{QP}$</span>. Most hardness assumptions used in crypto are in <span class="math-container">$\mathsf{NP}\cap\mathsf{coNP}$</span>, and a particular weak hardness assumption (fixed characteristic finite field discrete log) is known to be in <span class="math-container">$\mathsf{QP}$</span>. One can therefore interpret <span class="math-container">$\mathsf{NP} = \mathsf{QP}$</span> as &quot;most hardness assumptions in crypto are roughly comperable to fixed characteristic finite-field discrete log&quot;, which may work fine as motivation.</p>
<p>Still, is there any clearer motivation from a complexity theory point of view? For example a hierarchy collapse/something along those lines.</p>

CC BY-SA 4.0
2020-10-01T02:07:12.183Z
Violates ETH. Related: no known NP-complete problems are known to have subexp time complexity.
Joshua Grochow
CC BY-SA 4.0
2020-10-01T05:23:43.980Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-10-01T06:17:44.583Z
See also https://cstheory.stackexchange.com/questions/21571 for a related question about the inclusion $\mathrm{NP\subseteq QP}$ (without any exciting answers, I would say).
Emil Jeřábek
CC BY-SA 4.0
2020-10-01T15:22:55.260Z
@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.
Mark Schultz-Wu
CC BY-SA 4.0
2020-11-01T21:59:06.610Z
I have work on the problem P vs NP, I would like to discuss it, if interested answer this message.
Vinicius Ricardo
<cc.complexity-theory>
Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$
Mark Schultz-Wu
# Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$

(Asked by: username_0 on 2020-10-01)

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](https://cstheory.stackexchange.com/questions/38473/implication-of-exponential-time-hypothesis-falseness)), 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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Violates ETH. Related: no known NP-complete problems are known to have subexp time complexity.  
> **username_2**: 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.  
> **username_2**: See also https://cstheory.stackexchange.com/questions/21571 for a related question about the inclusion $\mathrm{NP\subseteq QP}$ (without any exciting answers, I would say).  
> **username_0**: @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.  
> **username_3**: I have work on the problem P vs NP, I would like to discuss it, if interested answer this message.  

---

## 1 answers

### Answer by username_2 on 2020-10-01. Score: 19 | Accepted answer

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})$?](https://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n).


---

