2
$\begingroup$

I am aware that $MA \subseteq ZPP^{NP} \subseteq \Sigma_2^{P}\cap \Pi_{2}^{P}$ and also $NP^{BPP} \subseteq MA \subseteq AM \subseteq \Pi_{2}^{P}$.

My question is: In this whole thing, where does $P^{NP}$ lie? (Obviously, $P^{NP} \subseteq ZPP^{NP}$) But, what about the relationship between $MA$ and $P^{NP}$? Which is contained in which one?

Intuitively, It is known that $MA_{EXP} \not\subset P/poly$, but for $EXP^{NP}$, no polynomial size circuit lower bound is known. Does that mean $P^{NP}$ is contained in $MA$?

$\endgroup$
1
$\begingroup$

Apparently, no relationship is known between $MA$ and $P^{NP}$. Even $BPP$ ($\subseteq MA$) vs $P^{NP}$ problem is still open. It is conjectured though that $MA = NP$ (Under standard hardness assumptions). So, it is likely that $MA \subseteq P^{NP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.