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?


2 Answers 2


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.

  • 1
    $\begingroup$ Why does 2 not hold directly for EXP? $\endgroup$
    – Ariel
    Commented Jul 31, 2020 at 6:46

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.