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, 2017 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$
    – user35837
    Apr 16, 2017 at 13:45
  • $\begingroup$ It would be ​ "for ALL conditions, that condition is true" . ​ ​ ​ ​ $\endgroup$
    – user12859
    Apr 16, 2017 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, 2017 at 14:17

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.