On the power of interaction

DOI10.1007/BF02122692zbMath0715.68028WikidataQ56959200 ScholiaQ56959200MaRDI QIDQ751809

Shafi Goldwasser, Johan T. Håstad, William Aiello

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

interactionsinteractive proofsoracleAM hierarchyIP hierarchyNP proof-system

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A Hierarchy Theorem for Interactive Proofs of Proximity, Randomness in interactive proofs

Cites Work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Are there interactive protocols for co-NP languages?
• Parity, circuits, and the polynomial-time hierarchy
• The knowledge complexity of interactive proof-systems