Arthur and Merlin as oracles (Q649095): Difference between revisions

Problems solvable in deterministic polynomial time given oracle access to the promise version of Arthur-Merlin class are studied. The authors prove that \(\mathrm{BPP}_{||}^{\mathrm{NP}} \subseteq \mathrm{P}_{||}^{\mathrm{prAM}}\) and \(\mathrm{S}_2^p \subseteq \mathrm{P}^{\mathrm{prAM}}\). In addition, new upper bounds for the classes \(\mathrm{S}_2^p\) and \(\mathrm{BPP}_{||}^{\mathrm{NP}}\) are provided. These upper bounds have consequences from a derandomization perspective. As corollaries for \(\mathrm{BPP}_{||}^{\mathrm{NP}} \subseteq \mathrm{P}_{||}^{\mathrm{prAM}}\) is shown that \(\mathrm{BPP}_{||}^{\mathrm{prAM}} = \mathrm{P}_{||}^{\mathrm{prAM}}\) and that \(\mathrm{BPP}_{||}^{\mathrm{NP}} \subseteq P^{\Sigma _2 ^p}\). From \(S_2^p \subseteq P^{\mathrm{prAM}}\) follows that if NP has polynomial size circuits, then \(\mathrm{PH} = \mathrm{P}^{\mathrm{prMA}}\). This fact is weaker than other known results, but has an unexpected proof. Another corollary is that \(\mathrm{FP}^{\mathrm{prMA}} \subseteq \mathrm{ZPP}^{\mathrm{NP}}\), which is a completely new result. Various results by Cai, Bshouty et al., Fortnow and al. can be proved in alternative ways based on the new results in this paper.