FOM: Probabilistic proofs

[Joe Shipman]

I agree with Harvey that probabilistic proofs should be (and are)
identified explicitly as such, that more examples from the literature
are needed in this discussion, and that probabilistic proofs do have a
sort of underlying rigor and deserve to be called "proofs" even when
distinguished from classical proofs.  A couple of additional points:

1) I think it's unlikely we will ever be able to convert probabilistic
proofs *automatically* into classical proofs, because even if a
"perfect" random-number generator were somehow to be provably
identified, I don't see how we could do better than prove that it will
make finitely many errors without being able to identify them.  (In the
same way, even if by some "principle of irrelevance" there exists a
sufficiently random P-time pseudo-random number generator for any
BPP-problem, that would only imply that BPP=P and not that *WE* could
find the P-time algorithm rather than an algorithm that made finitely
many errors [similarly if we had access to a truly algorithmically
random string we would still only know that using it misidentifies only
finitely many inputs to any random algorithm, not necessarily 0].)

2) Harvey's "imperfect implementation" appears to refer to the use of
pseudo-random number generators of unproved quality -- this is the
correct place to focus because the "imperfections" due to not having a
proof that the computer the calculation was run on is bug-free etc are
already there in computer-aided proofs like that of the 4CT which are
nonetheless accepted as real publishable proofs.  We presume we have a
handle on the latter type of imperfection if we are careful to reproduce
the calculation on independent systems (Nicely shows they need to be
independent at many different levels but that is still achievable)--we
implicitly assume that the probability of error in each verification is
independent (i.e. that there is not something spooky about the
particular calculation we are doing that induces bugs whenever
verification is attempted).

But this "scientific" assumption is not really different from assuming
that there is nothing spooky about the problem at hand that will induce
nonrandomness in physically generated random numbers used to run the
calculation.   This is an easier assumption to swallow than "the problem
does not induce nonrandomness in all polynomial-time pseudo-random
number generators" because some contrived problems can do exactly that
(though of course the contrivance is a diagonal algorithm that runs in
exponential time and is not [we believe] in BPP ).  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 the
probabilistic proof the same kind of status a computer-aided proof has
now.

I reiterate Harvey's call for examples of probabilistic proofs.  In
particular, can anyone suggest a candidate for "probabilistic proof"
that is not an instance of a BPP-problem?

-- Joe Shipman