[FOM] Non-constructive nature of probabilistic proofs

[Timothy Y. Chow]

Stephen Simpson wrote:

> I think Corfield is referring to the probabilistic method in finite
> combinatorics, as pioneered by Erd"os and expounded in the book by
> Erd"os and Spencer.

If you're referring to the book I'm thinking of, the main authors are
Alon and Spencer, with an appendix by Erdos.

> For those unfamiliar with the method, I want to point out that
> Corfield's description of it is seriously inaccurate.

Not "seriously inaccurate," just "informal."  The locution used by
Corfield is commonly used by practitioners; it's more concise and
suggestive than any pedantically correct alternative.

> Probabilistic existence proofs are non-constructive, in the sense that
> the proof does not produce a specific x such that P(x) holds.  Thus, the
> probabilistic method presents an obvious challenge for f.o.m.
> researchers.  In general, constructivity is an important f.o.m. issue,
> and the f.o.m. literature contains many interesting results concerning
> non-constructive existence proofs and the possibility of replacing them
> by constructive ones.

The sense in which probabilistic existence proofs are non-constructive is
an interesting question, and something that I've thought about a little
bit.  It's not nonconstructive in the sense that, for example, the proofs
of certain well-known theorems in number theory (e.g., Faltings's theorem
on rational points on curves of high genus) are nonconstructive.  The
latter do not even guarantee the existence of an algorithm to compute the
finite (or "non-infinite") sets of integers whose finitude is asserted by
the theorem.

In contrast, the typical situation in probabilistic combinatorics is that
the probabilistic existence proof is effective: just run through all the
(say) graphs of a certain size and check them for the desired property
until you hit paydirt.  So I think what people mean is that the proof does
not yield a *polynomial-time* algorithm for producing the desired entity.
This puts it in more in the realm of computational complexity than in the
realm of recursion theory or proof theory.

The situation is still not all that well understood, because a lot of
computational complexity focuses on decision problems, and here we're
interested in *constructing* objects.  So we're really interested not in
(for example) NP so much as TFNP (TF = total function) or, because of the
probabilistic angle here, TFBPP.  I'm not sure that anyone has even
formally defined and studied TFBPP.  Some months ago I came up with a
possible definition---basically to be in TFBPP an object has to be
constructible by an algorithm that generates candidates randomly, such
that testing whether a potential candidate is the real deal is a BPP
decision problem, and such that you get what you want in polynomial time.
Noga Alon suggested that Joel Friedman's "almost-Ramanujan" graphs (that I
mentioned elsewhere) provide an example of something known to be in TFBPP
but not known to be in TFP.  This turned out to be slightly trickier to
prove than I thought, but I believe it's true.  Anyway, I haven't really
developed these thoughts beyond the preliminary stage yet, although it
seems like a promising topic.

Tim