Skip to main content
2 of 6
edited title
user avatar
user avatar

Meyer's Theorem ([KL 80])

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

Proof Idea : 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 the bolded text written above paragraph .

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

user35837