Randomized proofs in arithmetic

DOI10.1007/BF02358994zbMATH Open0934.03075MaRDI QIDQ1807460FDOQ1807460

Authors: E. Ya. Dantsin 

Publication date: 22 November 1999

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

Recommendations

• Randomized algorithms in number theory
• Randomness in interactive proofs
• Randomness, pseudorandomness and models of arithmetic
• The computational content of arithmetical proofs
• Randomness below complete theories of arithmetic
• Proofs of Randomized Algorithms in Coq
• Proofs of randomized algorithms in Coq
• Randomized proof-labeling schemes
• Randomized proof-labeling schemes

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) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Cites Work

• Title not available (Why is that?)
• Alternation
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Arithmetization: A new method in structural complexity theory
• Classifying the computational complexity of problems

Cited In (8)

• A note on monte carlo primality tests and algorithmic information theory
• Randomization, persuasiveness and rigor in proofs
• Probabilistic verification of proofs in calculuses
• Proof-carrying data from arithmetized random oracles
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Proofs of randomized algorithms in Coq
• Random arithmetic formulas can be reconstructed efficiently
• Proofs of Randomized Algorithms in Coq

This page was built for publication: Randomized proofs in arithmetic

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