<ol>
<li><p>If $NP$ can be solved in quasipolynomial time, then $NP$ has quasi polynomial size circuit. </p></li>
<li><p>The second condition implies that the exponential time hierarchy collapses to the second level (as was shown in the <a href="http://dx.doi.org/10.1007/3-540-56287-7_99" rel="nofollow">paper</a> of Buhrman and Homer). It was improved the collapse to $S_2^{exp}$ in a <a href="http://www.sciencedirect.com/science/article/pii/S0304397507004859" rel="nofollow">paper</a> of Pavan et al.</p></li>
<li><p>As far as I know, these hypotheses do not easily imply a collapse of PH.</p></li>
</ol>

CC BY-SA 3.0
2016-10-13T05:45:41.530Z
2016-10-14T17:08:06.593Z
2016-10-14T17:08:06.593Z
Weidong
<p>By a translation argument, you can get that $QuasiNP \subseteq QuasiR/QuasiP$ and hence $PH \subseteq QuasiR/QuasiP$. I believe the second condition will imply a similar conclusion in terms of collapsing $PH$ to some level of "$QH$". </p>

<p>For the second part of your question, $EXP \subseteq p/poly \implies EXP = MA$. You can extend this result $EXP \subseteq p/quasi-poly \implies EXP = MATIME(Quasi)$.</p>

CC BY-SA 3.0
2016-10-12T08:10:36.743Z
NP=RP doesn't imply that PH collapses to RP, only to BPP. Why would the quasipolynomial case be different?
Emil Jeřábek
CC BY-SA 3.0
2016-10-12T08:14:25.033Z
Also, the quasipolynomial version of MA is closed under quasipolynomial reductions, whareas EXP is not (by the time-hierarchy theorem). Thus, the two classes are distinct (unconditionally). Presumably you only meant an inclusion.
Emil Jeřábek
CC BY-SA 3.0
2016-10-12T08:19:27.787Z
Oh, and "P/quasipoly" means "P with quasipolynomial advice". Since a P-machine has no time to read more than polynomially many bits of the advice anyway, this actually equals P/poly! The proper notation for the class of languages having circuits of size f(n) is SIZE(f(n)), but here QP/quasipoly would also do.
Emil Jeřábek
CC BY-SA 3.0
2016-10-13T08:32:19.647Z
@RickyDemer P is normally defined using regular TM, not random-access TM. Even so, the notation is ambiguous at best.
Emil Jeřábek
CC BY-SA 3.0
2016-10-11T16:08:06.097Z
2016-10-11T16:08:06.097Z
Ilya Volkovich
<p>Consider the following two scenarios:</p>

<ol>
<li>$NP\subseteq RTIME[2^{(\log n)^c}]$ or $NP\subseteq DTIME[2^{(\log n)^c}]$, i.e., $NP$ can be solved in quasipolynomial randomized or deterministic time. </li>
<li>$NP$ has quasipolynomial size circuits.</li>
</ol>

<p>Does the polynomial time hierarchy $PH$ collapse under any of the above conditions?</p>

<p>The first condition implies $EXP=NEXP$. Does the second imply the same or something weaker?</p>

<p>Could $P=BPP$ still hold in such situations?</p>

<hr>

<p>Separately what implications follow from $EXP=NEXP$ and/or $EXP$ having quasipolynomial circuits?</p>

<cc.complexity-theory>
Quasipolynomial and polynomial time hierarchy
Turbo
# Quasipolynomial and polynomial time hierarchy

(Asked by: username_0 on 2016-10-10)

Consider the following two scenarios:

1. $NP\subseteq RTIME[2^{(\log n)^c}]$ or $NP\subseteq DTIME[2^{(\log n)^c}]$, i.e., $NP$ can be solved in quasipolynomial randomized or deterministic time.
2. $NP$ has quasipolynomial size circuits.

Does the polynomial time hierarchy $PH$ collapse under any of the above conditions?

The first condition implies $EXP=NEXP$. Does the second imply the same or something weaker?

Could $P=BPP$ still hold in such situations?

---

Separately what implications follow from $EXP=NEXP$ and/or $EXP$ having quasipolynomial circuits?

**Tags:** cc.complexity-theory


---

## 2 answers

### Answer by username_1 on 2016-10-13. Score: 5

1. If $NP$ can be solved in quasipolynomial time, then $NP$ has quasi polynomial size circuit.
2. The second condition implies that the exponential time hierarchy collapses to the second level (as was shown in the [paper](http://dx.doi.org/10.1007/3-540-56287-7_99) of Buhrman and Homer). It was improved the collapse to $S\_2^{exp}$ in a [paper](http://www.sciencedirect.com/science/article/pii/S0304397507004859) of Pavan et al.
3. As far as I know, these hypotheses do not easily imply a collapse of PH.


---

### Answer by username_2 on 2016-10-11. Score: 4

By a translation argument, you can get that $QuasiNP \subseteq QuasiR/QuasiP$ and hence $PH \subseteq QuasiR/QuasiP$. I believe the second condition will imply a similar conclusion in terms of collapsing $PH$ to some level of "$QH$".

For the second part of your question, $EXP \subseteq p/poly \implies EXP = MA$. You can extend this result $EXP \subseteq p/quasi-poly \implies EXP = MATIME(Quasi)$.

> **Comments:**
> **username_3**: NP=RP doesn't imply that PH collapses to RP, only to BPP. Why would the quasipolynomial case be different?  
> **username_3**: Also, the quasipolynomial version of MA is closed under quasipolynomial reductions, whareas EXP is not (by the time-hierarchy theorem). Thus, the two classes are distinct (unconditionally). Presumably you only meant an inclusion.  
> **username_3**: Oh, and "P/quasipoly" means "P with quasipolynomial advice". Since a P-machine has no time to read more than polynomially many bits of the advice anyway, this actually equals P/poly! The proper notation for the class of languages having circuits of size f(n) is SIZE(f(n)), but here QP/quasipoly would also do.  
> **username_3**: @RickyDemer P is normally defined using regular TM, not random-access TM. Even so, the notation is ambiguous at best.  

---

