snippetMinor
How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$
Viewed 0 times
textsfsubseteqexpp_2polyprovesigmathenhow
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#54247, answer score: 6
Revisions (0)
No revisions yet.