Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes

DOI10.1016/0022-0000(88)90028-1zbMath0652.03029OpenAlexW2148957455WikidataQ56386804 ScholiaQ56386804MaRDI QIDQ1106840

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90028-1

zbMATH Keywords

Arthur-Merlin protocol efficient provability hierarchy of complexity classes randomized proof system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Algorithms for Group Isomorphism via Group Extensions and Cohomology, On Emulating Interactive Proofs with Public Coins, Complexity limitations on one-turn quantum refereed games, Explainable arguments, HyperPlonk: Plonk with linear-time prover and high-degree custom gates, (Nondeterministic) hardness vs. non-malleability, A coercion-resistant blockchain-based E-voting protocol with receipts, Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas, Structural complexity of rational interactive proofs, Linear Logic Proof Games and Optimization, ON HIGHER ARTHUR-MERLIN CLASSES, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Approximate counting in bounded arithmetic, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Playing Savitch and Cooking Games, How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge, The Complexity of Zero Knowledge, Sumcheck-based delegation of quantum computing to rational server, Unnamed Item, Unnamed Item, Polynomially Ambiguous Probabilistic Automata on Restricted Languages, Graph isomorphism is low for PP, Verifiable Stream Computation and Arthur--Merlin Communication, Communication Lower Bounds Using Directional Derivatives, Computational Integrity with a Public Random String from Quasi-Linear PCPs, On the complexity of approximating the VC dimension., In search of an easy witness: Exponential time vs. probabilistic polynomial time., On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Polynomially ambiguous probabilistic automata on restricted languages, Combinatorial techniques for universal hashing, Hardness vs randomness, On the complexity of interactive proofs with bounded communication, A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes, Quantum information and the PCP theorem, Multiple Usage of Random Bits in Finite Automata, The complexity of generating test instances, An information-theoretic treatment of random-self-reducibility, Probabilistic proof systems — A survey, On the power of multi-prover interactive protocols, New Limits to Classical and Quantum Instance Compression, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, A linear-time algorithm for the orbit problem over cyclic groups, Time- and space-efficient arguments from groups of unknown order, A Hierarchy Theorem for Interactive Proofs of Proximity, Recent results in hardness of approximation, Geometry and Combinatorics via Right-Angled Artin Groups, More on BPP and the polynomial-time hierarchy, On the hardness of computing the permanent of random matrices, Polynomial-time reducibilities and ``almost all oracle sets, Counting quantifiers, successor relations, and logarithmic space, The complexity of approximating a nonlinear program, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Zero-information protocols and unambiguity in Arthur-Merlin communication, A short note on Merlin-Arthur protocols for subset sum, A PCP theorem for interactive proofs and applications, On closure properties of bounded two-sided error complexity classes, Characterizing polynomial complexity classes by reducibilities, Solvable black-box group problems are low for PP, Succinct NP Proofs from an Extractability Assumption, Which languages have 4-round zero-knowledge proofs?, From private simultaneous messages to zero-information Arthur-Merlin protocols and back, Unnamed Item, Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Arthur and Merlin as oracles, Knottedness is in NP, modulo GRH, Inverting onto functions., Relations between average-case and worst-case complexity, Proofs of Proximity for Distribution Testing, Fault-tolerance and complexity (Extended abstract), Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Generalized Quantum Arthur--Merlin Games, An Exponential Separation Between MA and AM Proofs of Proximity, A hierarchy that does not collapse : alternations in low level space, The complexity of local dimensions for constructible sets, The complexity of debate checking, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, The reachability problem for finite cellular automata, If NP has polynomial-size circuits, then MA=AM, An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity, A framework for non-interactive instance-dependent commitment schemes (NIC), New collapse consequences of NP having small circuits, Arithmetization: A new method in structural complexity theory, Non-deterministic exponential time has two-prover interactive protocols, On the expression complexity of equivalence and isomorphism of primitive positive formulas, On the asymmetric complexity of the group-intersection problem, Graph isomorphism is low for PP, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Lower bounds for non-black-box zero knowledge, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Graph Isomorphism is in SPP, On zero error algorithms having oracle access to one query, Arthur and Merlin as Oracles, Isomorphism and canonization of tournaments and hypertournaments, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back, Placing conditional disclosure of secrets in the communication complexity universe, How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge, Randomized proofs in arithmetic, The Multiparty Communication Complexity of Set Disjointness, Which languages have 4-round fully black-box zero-knowledge arguments from one-way functions?, On the power of interaction, On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs, AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly, Proving properties of interactive proofs by a generalized counting technique, Elimination of parameters in the polynomial hierarchy, Private Coins versus Public Coins in Zero-Knowledge Proof Systems, The counting complexity of group-definable languages, Outsourcing computation: the minimal refereed mechanism, Interactive and probabilistic proof-checking, Constant-Round Interactive Proofs for Delegating Computation, On Dinur’s proof of the PCP theorem, Distributed interactive proofs for the recognition of some geometric intersection graph classes, The alternation hierarchy for sublogarithmic space is infinite, On the probabilistic closure of the loose unambiguous hierarchy, Statistical zero-knowledge languages can be recognized in two rounds, Pseudorandom bits for constant depth circuits, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority, PSPACE is provable by two provers in one round, \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs, Randomness in interactive proofs, On the undecidability of probabilistic planning and related stochastic optimization problems, PSPACE has constant-round quantum interactive proof systems

Cites Work