<p>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.</p>

CC BY-SA 3.0
2013-05-16T19:09:32.657Z
2013-05-16T19:09:32.657Z
domotorp
<p>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:</p>

<p>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. </p>

<p>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  \}.$</p>

<p>By simulation $M$ we have $L_{M} \in EXP \subseteq P/poly$. <em>If</em> using polynomial size circuits for $L_{M}$ we can construct a polynomial-size <em>multi-output</em> circuit $C$ such that $C(\langle x,i,t\rangle)=z$ <em>then</em> 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.</p>

<p>Question:</p>

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

<cc.complexity-theory><complexity-classes><conditional-results><polynomial-hierarchy>
On the proof of Meyer's Theorem
echuly
# On the proof of Meyer's Theorem

(Asked by: username_0 on 2013-05-15)

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?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, polynomial-hierarchy


---

## 1 answers

### Answer by username_1 on 2013-05-16. Score: 1 | Accepted answer

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.


---

