On the power of interaction

DOI10.1007/BF02122692MaRDI QIDQ751809zbMATH OpenWikidataFDO

Authors William Aiello, Johan Hastad, Shafi Goldwasser

Publication date 1990

Published in Combinatorica (Search for Journal in Brave)

zbMATH Keywords

interactionsoracleAM hierarchyinteractive proofsIP hierarchyNP proof-system

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 66620
• Finite state verifiers I
• scientific article; zbMATH DE number 4106274
• scientific article; zbMATH DE number 512981
• On the power of multi-prover interactive protocols

Cites work

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

Cited in

(13)

• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
• On the power of multi-prover interactive protocols
• A hierarchy theorem for interactive proofs of proximity
• Interactive proof systems with polynomially bounded strategies
• scientific article; zbMATH DE number 412256 (Why is no real title available?)
• Proving properties of interactive proofs by a generalized counting technique
• scientific article; zbMATH DE number 1754603 (Why is no real title available?)
• Does co-NP have short interactive proofs ?
• On interactive proofs with a laconic prover
• scientific article; zbMATH DE number 2077106 (Why is no real title available?)
• scientific article; zbMATH DE number 66620 (Why is no real title available?)
• Randomness in interactive proofs
• scientific article; zbMATH DE number 4080913 (Why is no real title available?)

This page was built for publication: On the power of interaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751809)