Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove :
If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$.
The previous similar theorem was
If $\textsf{NP} \subseteq \textsf{P/poly}$ then $\textsf{PH}=\Sigma_2^p$.
The second theorem was easy to prove as $\textsf{NP}=\Sigma_1^p$. But $\textsf{EXP}$ does not have such characteristic. How do I prove the first theorem. Any hints?
The more classical statement is that if $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \textsf{MA}$, due to Babai, Fortnow and Lund. Impagliazzo, Kabanets and Wigderson showed that $\textsf{NEXP} \subseteq \textsf{P/poly}$ iff $\textsf{NEXP} = \textsf{MA}$. See lecture notes of Bogdanov for proof sketches.
There is a more 'elementary' proof of the problem that doesn't involve the polynomial-encoding/self-correction ideas of BFL. The result appears in the original Karp-Lipton paper and is credited to Meyer. The way I think of it is like this:
Step 1: Show that EXP in P/poly implies EXP = PSPACE. Hints: Show that if M is an EXP-machine, the entries of the computation tableau of M(x) are computable from x in EXP. Conclude that they're computable in P/poly. Now in PSPACE, try all circuits, and check that all entries of the tableau are locally correct.
Step 2: Show that PSPACE in P/poly implies PSPACE = Sigma_2. Hints: Similarly, the tableau-contents-function of a PSPACE machine is in PSPACE, hence in P/poly. Now in Sigma_2, you can nondeterministically guess a circuit supposedly computing the tableau, and then conondeterministically verify its correctness.
Step 3: Combine Steps 2 and 3 together.
