# On the proof of Meyer's Theorem

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.

Question:

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

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.