14
$\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$ – T.... 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$ – T.... 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
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.