Given snapshot and boolean circuit how to compute coNP formula?

Question

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

Answer 1

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.