FOM: Reply to Pollack: machine-checked and probabilistic proofs
JSHIPMAN@bloomberg.net
JSHIPMAN at bloomberg.net
Thu Dec 18 16:44:46 EST 1997
Yes, the "trace" of a random algorithm only gives a conclusive proof if you can
believe the numbers used are random and that the physical computer performed as
advertised (though Rabin's algorithm is fast enough to be checked by hand).
I will read your "believing" paper. The problem you noted with "proofs by
random algorithm" is not a serious one, as one can appeal to published tables
of random numbers that were generated before the proof was even attempted. (To
use a deterministic pseudo-random number generator instead is to be in a state
of sin [Von Neumann's term] but the published tables are generated by "physical
means". By the way, I believe P=RP because I believe there exist for any
problem in RP polynomial-time pseudo-random-number-generators of a sufficient
degree of "irrelevance" -- a deterministic algorithm which simulates the random
algorithm using this generator, and makes enough trials that the "expected
number of errors" over all cases is finite [this is always possible] will then
solve the problem in polynomial time except for a finite number of cases, and
therefore some finite modification of it puts the problem in P.)
Thanks for your thoughtful comments!
-- Joe Shipman
More information about the FOM
mailing list