Theorem 6.20: If $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$ then $\mathsf{EXP\text{}} = \Sigma_2 ^{p}$.

My attempt : Let $L \in \mathsf{EXP\text{}}$. Then $L$ is computable by an $2^{p(n)}$-time Turing machine $M$, where $p$ is some polynomial. Let $x \in \{0,1\}^n $ be some input string. For every $i \in [2^{p(n)}] $, we denote by $z_i$ the encoding of the $i$th snapshot (the machine's state and symbols read by all heads) of $M'$s execution on input $x$. If $M$ has $k$ tapes, then $x\in L \iff $ for every $k+1$ indices $i,i_1,i_2,\cdots,i_k$, the snapshots $z_i,z_{i_{1}},\cdots,z_{i_{k}}$ satisfy some checkable criteria.

As $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$, then there is a $q(n)$-sized circuit $C$ (for some polynomial $q$) that computes $z_i$ from $i$. Now the main point is that the correctness of the transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate (namely, one that checks that the transcript satisfies all local criteria). Hence, $x\in L$ iff the following condition is true

$$ \exists C \in \{0,1\}^{q(n)} \forall i,i_1,i_2,\cdots,i_k \in \{0,1\}^{p(n)} T(x,C(i),C(i_1),\cdots,C(i_k)) = 1$$

Question : I am not able to understand, how transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate ?

Reference : http://theory.cs.princeton.edu/complexity/circuitschap.pdf

  • $\begingroup$ See Cook-Levin. ​ ​ $\endgroup$ – user12859 Apr 16 '17 at 13:24
  • $\begingroup$ @Ricky Demer I know from the table how to come up boolean formula but I don't know how to express it as a CoNP predicate. $\endgroup$ – aaag Apr 16 '17 at 13:45
  • $\begingroup$ It would be ​ "for ALL conditions, that condition is true" . ​ ​ ​ ​ $\endgroup$ – user12859 Apr 16 '17 at 13:51
  • 1
    $\begingroup$ Not really important, but if you have a single tape, the current snapshot depends on the snapshot in the previous step, to determine the new state and the new location of the head $i$, and the previous snapshot where the head was at location $i$ (to determine the current read symbol). So for $k=1$, your condition is on triplets of snapshots. $\endgroup$ – Ariel Apr 16 '17 at 14:17

You want to know how, given a circuit $C$, one can express the statement "given $i$, $C$ correctly computes $z_i$, the i'th snapshot in the computation of $M$ on some fixed input $x$", by a coNP predicate. Note that if this can be done, say using the predicate $\varphi (C,x)$, then $$\psi(x)=\exists C: \varphi(C,x)\land C\left(2^{|x|^c}\right) \text{ is accepting}$$

is exactly the $\Sigma_2$ formula you're looking for. To see why, note that $x\in L$ iff the last snapshot is accepting, or equivalently if $C\left(2^{|x|^c}\right)$ is accepting, and $C(i)$ correctly computes $z_i$. So if $\varphi(C,x)$ indeed expresses "C correctly computes $M$'s snapshots on input $x$", then $x\in L \iff \psi(x)$. If you have a guarantee that polynomial circuits for $L$ exist, then you can bound the existential quantifier, and only look for poly-size circuits.

So how do we write $\varphi(C,x)$ as a coNP predicate? Using locality, you know that the $i'th$ snapshot depends on some $k$ previous ones (where $k$ is a constant depending on the number of tapes). $C$ correctly computes the snapshots if for all $i,i_1,...,i_k$ (this gives you the universal quantifier) it holds that $T\left(x, C(i), C(i_1),...,C(i_k)\right)$, where $T$ depends on $M$'s transition function. Intuitively, $T$ checks whether $i_1,...,i_k$ are the previous indicies of snapshots who determine $z_i$, and if so verifies that the transition was indeed according to $M$'s rules.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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