<p>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 <a href="https://arxiv.org/abs/1806.08872" rel="nofollow noreferrer">Dietrich &amp; Wilson's</a> notion of &quot;groups of black box type&quot;, and is in the spirit of <a href="https://doi.org/10.1137/1.9781611970395" rel="nofollow noreferrer">Hartmanis's &quot;provable complexity.&quot;</a>) Towards this end, we consider:</p>
<blockquote>
<p><strong>Definition</strong>: &quot;Certified <span class="math-container">$\mathsf{P/poly}$</span>&quot; or &quot;<span class="math-container">$\mathsf{Cert}$</span>-<span class="math-container">$\mathsf{P/poly}$</span>&quot; consists of those languages <span class="math-container">$L$</span> such that <span class="math-container">$L$</span> is in <span class="math-container">$\mathsf{P/poly}$</span> and there is a poly-bounded certification of this fact. More precisely, <span class="math-container">$L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$</span> if there exists a poly-time <span class="math-container">$V$</span>, and for all <span class="math-container">$n$</span>, there exists <span class="math-container">$C_n, \pi_n$</span> with <span class="math-container">$\max\{|C_n|,|\pi_n|\} \leq poly(n)$</span> such that</p>
<ol>
<li><p><span class="math-container">$V$</span> is a Cook-Reckhow proof system for the language <span class="math-container">$\{C : C \text{ correctly computes } L \text{ at length } \ell=\text{# inputs to C}\}$</span>, that is (a) If <span class="math-container">$C(x) = L(x)$</span> for all <span class="math-container">$x \in \Sigma^\ell$</span>, where <span class="math-container">$\ell$</span> is the number of inputs to <span class="math-container">$C$</span>, then there exists a <span class="math-container">$\pi$</span> such that <span class="math-container">$V(C,\pi)=1$</span> and (b) If there is <span class="math-container">$x \in \Sigma^\ell$</span> such that <span class="math-container">$C(x) \neq L(x)$</span>, then there is no <span class="math-container">$\pi$</span> such that <span class="math-container">$V(C,\pi)=1$</span>.</p>
</li>
<li><p>For all <span class="math-container">$n$</span>, <span class="math-container">$C_n$</span> has <span class="math-container">$n$</span> inputs and <span class="math-container">$V(C_n,\pi_n)=1$</span>.</p>
</li>
</ol>
</blockquote>
<p>Then <span class="math-container">$\mathsf{Cert}\text{-}\mathsf{P/poly}$</span> contains <span class="math-container">$\mathsf{NPSV}_t$</span>-uniform <span class="math-container">$\mathsf{P/poly}$</span>, so it is probably not just <span class="math-container">$\mathsf{P}$</span>. And we have the desired statement:</p>
<blockquote>
<p><strong>Proposition</strong>: <span class="math-container">$\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}$</span>.</p>
</blockquote>
<p><em>Proof</em>: First we show that <span class="math-container">$\mathsf{Cert}\text{-}\mathsf{P/poly} \subseteq \mathsf{NP}$</span>, giving the final &quot;<span class="math-container">$\Longrightarrow$</span>&quot; in the statement. Suppose <span class="math-container">$L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$</span> with verifier <span class="math-container">$V$</span> and <span class="math-container">$V$</span>-verified circuit family <span class="math-container">$\{(C_n,\pi_n)\}_{n=1,2,3,...}$</span>. The following is a nondeterministic poly-time algorithm for <span class="math-container">$L$</span>: on input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, guess <span class="math-container">$C_n,\pi_n$</span>, and run <span class="math-container">$V(C_n,\pi_n)$</span>; if it accepts, then output <span class="math-container">$C_n(x)$</span>.</p>
<p>Next, we show that Certified <span class="math-container">$\mathsf{P/poly}$</span> is closed under complement, giving the first &quot;<span class="math-container">$\Longleftrightarrow$</span>&quot; in the statement. Suppose <span class="math-container">$L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$</span>, with verifier <span class="math-container">$V$</span> as in the above definition. Since <span class="math-container">$L \in \mathsf{NP}$</span> by the preceding paragraph, there is some <span class="math-container">$c$</span> such that <span class="math-container">$L \in \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(2^{n^c})$</span>. Let <span class="math-container">$V'(C',\pi)$</span> compute as follows: if <span class="math-container">$C'$</span> has a negation gate as its output gate, then write <span class="math-container">$C' = \neg C$</span>, and define <span class="math-container">$V'(C',\pi) = V(C,\pi)$</span>. Otherwise, <span class="math-container">$V'(C',\pi)$</span> checks whether <span class="math-container">$|\pi|=2^{\ell + \ell^c}$</span> (where <span class="math-container">$\ell$</span> is the number of inputs to <span class="math-container">$C'$</span>); if not, then <span class="math-container">$V'$</span> rejects, and if so, then <span class="math-container">$V'$</span> simply enumerates all strings <span class="math-container">$y$</span> of length <span class="math-container">$\ell$</span>, and checks whether <span class="math-container">$C'(y)=L(y)$</span>, using the <span class="math-container">$2^{\ell^c}$</span> deterministic algorithm for <span class="math-container">$L$</span>, which takes time <span class="math-container">$poly(|\pi|)$</span>. (This latter yoga was needed to make sure that <span class="math-container">$V'$</span> satisfies property 1 in the definition.) If <span class="math-container">$\{(C_n,\pi_n)\}$</span> is a certified family of circuits for <span class="math-container">$L$</span> with verifier <span class="math-container">$V$</span>, then <span class="math-container">$\{(\neg C_n, \pi_n)\}$</span> is a certified family of circuits for <span class="math-container">$L^c$</span> with verifier <span class="math-container">$V'$</span>. QED</p>

CC BY-SA 4.0
2019-10-28T20:58:24.347Z
2019-10-28T20:58:24.347Z
2020-06-17T09:38:08.363Z
Joshua Grochow
<p>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}$$</p>

<blockquote>
  <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?</p>
  
  <p>Is there a possible similar collapse result from non-circuit containment?</p>
</blockquote>

<p><strong>Conjecture</strong>: </p>

<blockquote>
  <p>Such result does not exist.</p>
</blockquote>

CC BY-SA 3.0
2015-04-25T14:39:54.137Z
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?
Joshua Grochow
CC BY-SA 3.0
2015-04-25T18:00:01.400Z
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?
Turbo
CC BY-SA 3.0
2015-04-25T18:11:46.487Z
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$?
Joshua Grochow
CC BY-SA 3.0
2015-04-25T18:14:09.630Z
Could you provide link to theorems of Fortune, Mahaney, and Ogihara-Watanabe?
Turbo
CC BY-SA 3.0
2015-04-25T18:23:07.970Z
http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html
Joshua Grochow
CC BY-SA 3.0
2015-04-25T18:30:46.063Z
Sorry I think I have misunderstood your statement then. I thought theorems of Fortune, Mahaney, and Ogihara-Watanabe give collapse to first level but not lower.
Turbo
CC BY-SA 3.0
2015-04-25T19:23:45.097Z
No - sorry for the ambiguity in the parsing of my first comment. They give collapses to P (the zero-th level). This also implies a collapse to the first level, but in a trivial sort of way that I think you want to rule out?
Joshua Grochow
CC BY-SA 3.0
2015-04-25T19:34:46.617Z
Oh Yes. I will update that.
Turbo
<cc.complexity-theory><circuit-complexity>
What would signify hierarchy collapse to first level?
Turbo
# What would signify hierarchy collapse to first level?

(Asked by: username_0 on 2015-04-25)

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.

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_1**: 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$?  
> **username_0**: Could you provide link to theorems of Fortune, Mahaney, and Ogihara-Watanabe?  
> **username_1**: http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html  
> **username_0**: Sorry I think I have misunderstood your statement then. I thought theorems of Fortune, Mahaney, and Ogihara-Watanabe give collapse to first level but not lower.  
> **username_1**: No - sorry for the ambiguity in the parsing of my first comment. They give collapses to P (the zero-th level). This also implies a collapse to the first level, but in a trivial sort of way that I think you want to rule out?  
> **username_0**: Oh Yes. I will update that.  

---

## 1 answers

### Answer by username_1 on 2019-10-28. Score: 1 | Accepted answer

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](https://arxiv.org/abs/1806.08872) notion of "groups of black box type", and is in the spirit of [Hartmanis's "provable complexity."](https://doi.org/10.1137/1.9781611970395)) 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


---

