Proving properties of interactive proofs by a generalized counting technique

DOI10.1016/0890-5401(89)90053-9zbMath0684.68068OpenAlexW2023141434MaRDI QIDQ1825663

László Babai, Shlomo Moran

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90053-9

zbMATH Keywords

interactive proofsinteractive protocolIP hierarchyArthur Merlin game

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Results on resource-bounded measure, Randomness in interactive proofs

Cites Work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Universal classes of hash functions
• The knowledge complexity of interactive proof-systems
• Unnamed Item