On the power of interaction

DOI10.1007/BF02122692zbMATH Open0715.68028WikidataQ56959200 ScholiaQ56959200MaRDI QIDQ751809FDOQ751809

Authors: William Aiello, Johan Hastad, Shafi Goldwasser 

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

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

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)

Cites Work

• The knowledge complexity of interactive proof-systems
• Parity, circuits, and the polynomial-time hierarchy
• 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?

Cited In (13)

• Randomness in interactive proofs
• On the power of multi-prover interactive protocols
• Interactive proof systems with polynomially bounded strategies
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A hierarchy theorem for interactive proofs of proximity
• Does co-NP have short interactive proofs ?
• On interactive proofs with a laconic prover
• Proving properties of interactive proofs by a generalized counting technique
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

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)