AM (complexity)

AM (complexity) AM is a probabilistic complexity class capturing decision problems solvable by an interactive randomized protocol between a polynomial-time verifier and an untrusted prover with bounded rounds. It generalizes nondeterministic verification by allowing randomness and interaction, and it connects to major results and conjectures in computational complexity, cryptography, and pseudorandomness.

Definition

AM is defined via a two-message Arthur–Merlin protocol introduced by László Babai, Shafi Goldwasser, and Silvio Micali (often cited with Russell Impagliazzo and Carlo G. F. Goldschlager in related literature), where a probabilistic polynomial-time verifier called Arthur sends random bits to an all-powerful prover called Merlin, who responds with a proof string. The verifier then runs a deterministic polynomial-time predicate to accept or reject. Completeness and soundness are specified so that members of the language yield acceptance with high probability, while nonmembers yield acceptance with low probability. This class is closely tied to interactive proofs such as those studied by László Babai, Shafi Goldwasser, and Silvio Micali, and formalized in later surveys by Oded Goldreich and Noam Nisan.

Relationships to Other Complexity Classes

AM sits between several well-known classes: it contains NP and is contained in NP with randomness under certain relativized settings, while AM is contained in Π2P under classical hierarchies and relates to MA as a randomized analogue of NP. AM is contained in AM-equivalent formulations like public-coin interactive proofs studied by Carsten Lund and Rajeev Motwani, and it is subsumed by classes such as IP and PSPACE via results by Adrian Fortnow and Lance Fortnow. AM has nontrivial connections to statistical zero-knowledge classes like SZK explored by Dana Angluin and Moni Naor as well as to probabilistic classes like BPP and derandomization results by Noam Nisan and Avraham Impagliazzo. Relativizations by oracles constructed by Bennett and Gill demonstrate separations and collapses among AM, PH, and BPP under different hypotheses. Reductions and equivalences involving AM feature prominently in work by Michele Sipser, Daniel Spielman, and Russell Impagliazzo.

Complete Problems and Canonical Languages

Unlike NP with SAT, AM lacks a single canonical complete problem under polynomial-time many-one reductions in the usual sense; nevertheless, several problems are AM-complete under randomized reductions or promise variants. Canonical promise problems include variants of Graph Non-Isomorphism studied by László Babai and interactive protocols for Group Non-Membership explored by Michel Ben-Or and Oded Goldreich. Statistical closeness and certain promise variants of approximate counting, such as approximate set size or approximate permanent estimations considered by Leslie Valiant and Mihai Nica, serve as natural complete targets. Search problems connected to AM arise in cryptographic contexts examined by Silvio Micali, Moni Naor, and Oded Goldreich where hardness assumptions yield promise AM-complete languages.

Proof Systems and Alternate Characterizations

AM admits multiple characterizations: as public-coin two-round interactive proofs (Arthur–Merlin protocols) formalized by László Babai and Eugene Kushilevitz, and equivalently via randomized polynomial-time machines with access to nondeterministic advice under certain error reductions explored by Moses Charikar and Shafi Goldwasser. AM can be characterized using hitting set and pseudorandom generator frameworks investigated by Noam Nisan and David Zuckerman; derandomization results tie AM to deterministic simulation techniques developed by Russell Impagliazzo and William Gasarch. Connections to zero-knowledge proof systems are highlighted by work of Oded Goldreich and Silvio Micali, showing that some AM protocols can be transformed into statistical zero-knowledge proofs under cryptographic assumptions studied by Ronald Rivest and Adi Shamir.

Containment, Collapse Results, and Open Problems

Key results include containment of AM in the second level of the polynomial hierarchy under specific assumptions, and demonstrations that if certain derandomization hypotheses by Noam Nisan and Noam Nisan (notably hardness vs randomness paradigms by Alexander A. Razborov and Mikko M. H. Sipser) hold, AM collapses to simpler classes like NP or MA. Oracle separations constructed by Bennett and John Gill show that relativized worlds can force AM outside PH or coincide with it, making unconditional separations difficult. Open problems center on whether AM equals NP, whether AM collapses to MA or to BPP under plausible circuit lower bounds by researchers like Valerie King and Alexander Razborov, and whether there exist natural complete languages for AM under deterministic reductions—a question pursued by Leslie Valiant and Avi Wigderson. Another significant frontier asks whether cryptographic primitives developed by Whitfield Diffie, Martin Hellman, and Ronald Rivest imply separations or containments involving AM, and whether advances in pseudorandom generator constructions by Noam Nisan and Gábor Tardos will yield unconditional derandomization of AM.

Category:Complexity classes