# What would signify hierarchy collapse to first level?

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.

• 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? Apr 25 '15 at 14:39
• 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?
– Mr.
Apr 25 '15 at 18:00
• 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$? Apr 25 '15 at 18:11
• Could you provide link to theorems of Fortune, Mahaney, and Ogihara-Watanabe?
– Mr.
Apr 25 '15 at 18:14
• blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html Apr 25 '15 at 18:23

It is perhaps reasonable to think that circuits that people would come up with would come along with easily verifiable proofs of their correctness. (This was indirectly inspired by Dietrich & Wilson's notion of "groups of black box type", and is in the spirit of Hartmanis's "provable complexity.") Towards this end, we consider:

Definition: "Certified $$\mathsf{P/poly}$$" or "$$\mathsf{Cert}$$-$$\mathsf{P/poly}$$" consists of those languages $$L$$ such that $$L$$ is in $$\mathsf{P/poly}$$ and there is a poly-bounded certification of this fact. More precisely, $$L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$$ if there exists a poly-time $$V$$, and for all $$n$$, there exists $$C_n, \pi_n$$ with $$\max\{|C_n|,|\pi_n|\} \leq poly(n)$$ such that

1. $$V$$ is a Cook-Reckhow proof system for the language $$\{C : C \text{ correctly computes } L \text{ at length } \ell=\text{# inputs to C}\}$$, that is (a) If $$C(x) = L(x)$$ for all $$x \in \Sigma^\ell$$, where $$\ell$$ is the number of inputs to $$C$$, then there exists a $$\pi$$ such that $$V(C,\pi)=1$$ and (b) If there is $$x \in \Sigma^\ell$$ such that $$C(x) \neq L(x)$$, then there is no $$\pi$$ such that $$V(C,\pi)=1$$.

2. For all $$n$$, $$C_n$$ has $$n$$ inputs and $$V(C_n,\pi_n)=1$$.

Then $$\mathsf{Cert}\text{-}\mathsf{P/poly}$$ contains $$\mathsf{NPSV}_t$$-uniform $$\mathsf{P/poly}$$, so it is probably not just $$\mathsf{P}$$. And we have the desired statement:

Proposition: $$\mathsf{NP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longleftrightarrow \mathsf{coNP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longrightarrow \mathsf{PH} = \mathsf{\Sigma_1 P} = \mathsf{\Pi_1 P}$$.

Proof: First we show that $$\mathsf{Cert}\text{-}\mathsf{P/poly} \subseteq \mathsf{NP}$$, giving the final "$$\Longrightarrow$$" in the statement. Suppose $$L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$$ with verifier $$V$$ and $$V$$-verified circuit family $$\{(C_n,\pi_n)\}_{n=1,2,3,...}$$. The following is a nondeterministic poly-time algorithm for $$L$$: on input $$x$$ of length $$n$$, guess $$C_n,\pi_n$$, and run $$V(C_n,\pi_n)$$; if it accepts, then output $$C_n(x)$$.

Next, we show that Certified $$\mathsf{P/poly}$$ is closed under complement, giving the first "$$\Longleftrightarrow$$" in the statement. Suppose $$L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$$, with verifier $$V$$ as in the above definition. Since $$L \in \mathsf{NP}$$ by the preceding paragraph, there is some $$c$$ such that $$L \in \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(2^{n^c})$$. Let $$V'(C',\pi)$$ compute as follows: if $$C'$$ has a negation gate as its output gate, then write $$C' = \neg C$$, and define $$V'(C',\pi) = V(C,\pi)$$. Otherwise, $$V'(C',\pi)$$ checks whether $$|\pi|=2^{\ell + \ell^c}$$ (where $$\ell$$ is the number of inputs to $$C'$$); if not, then $$V'$$ rejects, and if so, then $$V'$$ simply enumerates all strings $$y$$ of length $$\ell$$, and checks whether $$C'(y)=L(y)$$, using the $$2^{\ell^c}$$ deterministic algorithm for $$L$$, which takes time $$poly(|\pi|)$$. (This latter yoga was needed to make sure that $$V'$$ satisfies property 1 in the definition.) If $$\{(C_n,\pi_n)\}$$ is a certified family of circuits for $$L$$ with verifier $$V$$, then $$\{(\neg C_n, \pi_n)\}$$ is a certified family of circuits for $$L^c$$ with verifier $$V'$$. QED