4
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

  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 of Buhrman and Homer). It was improved the collapse to $S_2^{exp}$ in a paper of Pavan et al.

  3. As far as I know, these hypotheses do not easily imply a collapse of PH.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ NP=RP doesn't imply that PH collapses to RP, only to BPP. Why would the quasipolynomial case be different? $\endgroup$
    – Emil Jeřábek
    Commented Oct 12, 2016 at 8:10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Oct 12, 2016 at 8:14
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Oct 12, 2016 at 8:19
  • 1
    $\begingroup$ @EmilJeřábek : ​ I don't see how that works, since the input can affect which advice bits the machine reads. ​ ​ ​ ​ $\endgroup$
    – user6973
    Commented Oct 13, 2016 at 6:11
  • $\begingroup$ @RickyDemer P is normally defined using regular TM, not random-access TM. Even so, the notation is ambiguous at best. $\endgroup$
    – Emil Jeřábek
    Commented Oct 13, 2016 at 8:32

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.