FOM: Probabilistic proofs
Stephen Cook
sacook at cs.toronto.edu
Tue Sep 22 16:40:47 EDT 1998
Joe Shipman just wrote
If we are to get
"reproducibility" we must use either previously published tables of
physically generated random bits or deterministic pseudo-random number
generators; I claim that the first choice ought to allow us to give th
e
probabilistic proof the same kind of status a computer-aided proof has
now.
An adversarial mathematician might study a previously published table of
physically generated random bits and use it to devise an input for which the
probabilistic algorithm gives a wrong answer, and hence publish a "proof"
of a false theorem. This may not be possible in the case of Rabin's test,
but should be quite possible in the case of Schwartz' test. (Find nonsingular
matrix of polynomials which is singular for all integer values given by the
random bits on the part of the table used.)
Steve Cook
More information about the FOM
mailing list