Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} $. A proof outline is as follows:

Let $L \in EXP $ and let $M$ be a one tape TM deciding $L$ in time $2^{n^{C}}$. Consider the computation tableau for $M$, and assume each position $(i,t)$ encodes as a string $z_{i,t}$ the content all cell at time $t$, whether the head of the tape scanning cell $i$ at time $t$, and if it is, records the internal state $q$ of the TM.

Now consider the language about computational historical tableau of $M$. Let $L_{M} = \{ \langle x,i,t,z\rangle | \text{on input } x \text{ we have } z_{i,t} = z \text{ for } M \}.$

By simulation $M$ we have $L_{M} \in EXP \subseteq P/poly$. If using polynomial size circuits for $L_{M}$ we can construct a polynomial-size multi-output circuit $C$ such that $C(\langle x,i,t\rangle)=z$ then we get a characterization with two quantifiers $L_{M} = \exists C \in \{0,1\}^{poly(n)},\forall i ,t\in \{0,1\}^{poly(n)},C(\langle x,i,t\rangle)$ follow from $C(\langle x,i-1,t-1\rangle),C(\langle x,i,t-1\rangle),C(\langle x,i-1,t-1\rangle) \wedge C(\langle x,1,2^{n^{C}}\rangle) $ is the accepting state by the transition function of the TM.


In this proof, I am not sure about the construction of multi-output circuit. Can anyone give a concrete way of doing this construction?


1 Answer 1


I am not sure I understand your question. Let $L_M(k)=\{(x,i,t)$ for which on input $x$ we have that the $k$-th bit of $z_{i,t}$ is $1$. This language is in EXP, thus also in P/poly. Putting together these circuits for different values of $k$, we get the multi-output circuit.


Your Answer

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

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