|
Zapiski Nauchnykh Seminarov POMI, 1995, Volume 220, Pages 49–71
(Mi znsl4280)
|
|
|
|
Randomized proofs in arithmetic
E. Ya. Dantsin St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
A randomized proof system for arithmetic is introduced. A proof of an arithmetical formula is defined as its derivation from the axioms of arithmetic by the standard rules of inference of arithmetic and also one more rule which we call the random substitution rule. Such proofs can be regarded as a special kind of interactive proof and, more exactly, as a special kind of the Arthur–Merlin proofs. The main result of the paper shows that a proof in arithmetic with the random substitution rule can be considerably shorter than an arithmetical proof of the same formula. Namely, there exists a set or formulas such that (i) these fo nulas are provable in arithmetic but, unless $\mathrm{PSPACE}=\mathrm{NP}$, do not have polynomially long proofs; (ii) these proofs have polynomially long proofs in arithmetic with random substitution (whatever random numbers appear) and the probability of error of these proofs is exponentially small. Bibliography: 10 titles.
Received: 18.11.1994
Citation:
E. Ya. Dantsin, “Randomized proofs in arithmetic”, Studies in constructive mathematics and mathematical logic. Part IX, Zap. Nauchn. Sem. POMI, 220, POMI, St. Petersburg, 1995, 49–71; J. Math. Sci. (New York), 87:1 (1997), 3209–3220
Linking options:
https://www.mathnet.ru/eng/znsl4280 https://www.mathnet.ru/eng/znsl/v220/p49
|
Statistics & downloads: |
Abstract page: | 100 | Full-text PDF : | 33 |
|