Randomized proofs in arithmetic

DOI10.1007/BF02358994zbMath0934.03075MaRDI QIDQ1807460

Evgeny Dantsin

Publication date: 22 November 1999

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

zbMATH Keywords

interactive proofrandomized proof systemArthur-Merlin proofsrandom substitution rule

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items (1)

Probabilistic verification of proofs in calculuses

Cites Work

• Unnamed Item
• Arithmetization: A new method in structural complexity theory
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Classifying the computational complexity of problems
• The Knowledge Complexity of Interactive Proof Systems
• Alternation
• Algebraic methods for interactive proof systems
• IP = PSPACE

This page was built for publication: Randomized proofs in arithmetic