[FOM] Re: Non-constructive nature of probabilistic proofs

[Timothy Y. Chow]

On Mon 3 Nov I wrote:

>I'm not sure that anyone has even formally defined and studied TFBPP.
>Some months ago I came up with a possible definition

Let me say a little bit more about this.  It might seem natural to say
that a probabilistic existence proof is nonconstructive if it does not
directly yield an explicit polynomial-time algorithm for constructing the
object whose existence it proves.  I suggest, however, a slightly
different definition.  If the proof yields a *randomized* algorithm that
runs in polynomial time and yields a positive instance with a bounded
probability of error, then I think the proof deserves to be called
"constructive."  This is a more generous definition of constructive.  For
example, consider a BPP property that 1/n of all graphs on n vertices
enjoy.  Then I can construct an instance by randomly generating a linear
number of graphs on n vertices and testing each of them for the property.
I consider this "constructive" even though maybe it's not an "explicit"
construction.

Some probabilistic proofs are constructive in this sense although they
may not be "explicitly" constructive---Joel Friedman's almost-Ramanujan
graphs furnish an example.  Other probabilistic proofs are nonconstructive
even with my more generous notion of constructiveness.  A classic example
is the existence proof of Ramsey graphs---graphs on n vertices with no
clique or independent set with more than 2 log_2 n vertices.  Even though
you can randomly generate graphs on n vertices and expect to get a Ramsey
graph in polynomial time, there isn't any (known) efficient (i.e., BPP)
way of identifying a Ramsey graph when you get one.

Tim