Arthur and Merlin as oracles
type: Item
instance of: scholarly article
title: Arthur and Merlin as oracles
zbMATH Open document ID: 1248.68201
author: Venkatesan T. Chakaravarthy
author: Sambuddha Roy
published in: Computational Complexity
publication date: 2011-11-30T00:00:00Z
review text: 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.
reviewed by: Mihai Prunescu
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5982630
zbMATH Keywords: symmetric alternation
zbMATH Keywords: Karp-Lipton theorem
zbMATH Keywords: learning circuits
zbMATH Keywords: zero-sum games
zbMATH Keywords: boolean matrices
zbMATH Keywords: near-optimal strategies
zbMATH Keywords: conditional derandomization
MaRDI profile type: Publication
full work available at URL: s00037-011-0015-3
OpenAlex ID: W2028556586
cites work: On sparse approximations to randomized strategies and convex combinations
cites work: On pseudorandomness and resource-bounded measure
cites work: If NP has polynomial-size circuits, then MA=AM
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Oracles and queries that are sufficient for exact learning
cites work: \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
cites work: More on BPP and the polynomial-time hierarchy
cites work: Oblivious Symmetric Alternation
cites work: Arthur and Merlin as Oracles
cites work: On the complexity of succinct zero-sum games
cites work: Proving SAT does not have small circuits with an application to the two queries problem
cites work: Q4526985
cites work: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
cites work: New Collapse Consequences of NP Having Small Circuits
cites work: Simple strategies for large zero-sum games with applications to complexity theory
cites work: Derandomizing Arthur-Merlin games using hitting sets
cites work: Private vs. common random bits in communication complexity
cites work: Hardness vs randomness
cites work: Symmetric alternation captures BPP
cites work: Pseudorandomness for approximate counting and sampling
DOI: 10.1007/S00037-011-0015-3
description: scientific article; zbMATH DE number 5982630