FOM: Reply to Pollack: machine-checked and probabilistic proofs

[JSHIPMAN@bloomberg.net]

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