13
$\begingroup$

We know that $$\mathsf{NP\subseteq P/Poly \iff coNP\subseteq P/Poly\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P}$$ $$\mathsf{NP\subseteq P/Log\iff coNP\subseteq P/Log\implies PH=\Sigma_0^P=\Pi_0^P}$$

Is there any circuit result that could imply $$\mathsf{PH=\Sigma_1^P=\Pi_1^P}$$ but still $$\mathsf{PH\neq\Sigma_0^P=\Pi_0^P}$$ is a possibility?

Is there a possible similar collapse result from non-circuit containment?

Conjecture:

Such result does not exist.

$\endgroup$
  • 4
    $\begingroup$ NP in P/log implies P=NP, not just that PH collapses to the second level. Presumably you want a collapse to NP but not all the way to P (which also happens the theorems of Fortune, Mahaney, and Ogihara-Watanabe)? Also, do you mean a bound of the form "[uniform class] is contained in [circuit class]"? "NP is contained in [circuit class]"? Or really an arbitrary circuit bound? $\endgroup$ – Joshua Grochow Apr 25 '15 at 14:39
  • $\begingroup$ I think it would be nice to see a class containment(preferably NP) in a circuit class giving collapse to first level, analogous to collapse to 2nd and 0th level as above. Is there a reference for collapse to NP but not to P results. What circut bound are you thinking? $\endgroup$ – Turbo Apr 25 '15 at 18:00
  • 1
    $\begingroup$ I don't have a particular one in mind. I was mostly just pointing out that your question boils down to: What complexity class containments (circuit or otherwise) imply $P \neq NP = coNP$? $\endgroup$ – Joshua Grochow Apr 25 '15 at 18:11
  • $\begingroup$ Could you provide link to theorems of Fortune, Mahaney, and Ogihara-Watanabe? $\endgroup$ – Turbo Apr 25 '15 at 18:14
  • 1
    $\begingroup$ blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html $\endgroup$ – Joshua Grochow Apr 25 '15 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.