Arthur and Merlin as oracles (Q649095): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00037-011-0015-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2028556586 / rank | |||
Normal rank |
Revision as of 03:02, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Arthur and Merlin as oracles |
scientific article |
Statements
Arthur and Merlin as oracles (English)
0 references
30 November 2011
0 references
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.
0 references
symmetric alternation
0 references
Karp-Lipton theorem
0 references
learning circuits
0 references
zero-sum games
0 references
boolean matrices
0 references
near-optimal strategies
0 references
conditional derandomization
0 references