0
$\begingroup$

By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.

Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).

By using the padding technique, we can conclude from this $MA_{EXP} \subseteq EXP^{NP} \not\subset P/poly$ and hence yielding a circuit lower bound for $EXP^{NP}$.

What is wrong with this argument?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ We don't know that $MA\subseteq P^{NP}$. $\endgroup$
    – Ariel
    Commented Dec 19, 2017 at 6:00
  • $\begingroup$ @Ariel I found this on Fortnow blog [Link: blog.computationalcomplexity.org/2002/12/… ]: MA is also contained in many of the same classes BPP is contained in, including $S_2^P$ (See 6th Paragraph) $\endgroup$
    – Pawan Kumar
    Commented Dec 19, 2017 at 6:11
  • 1
    $\begingroup$ This is a different class, see zoo entry $\endgroup$
    – Ariel
    Commented Dec 19, 2017 at 6:26
  • $\begingroup$ @Ariel Yes. Got it. I wrongly interpreted $S_{2}^{P}$ same as $\Delta_{2}^{P}$. Thanks for the clarification. $\endgroup$
    – Pawan Kumar
    Commented Dec 19, 2017 at 6:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.