[FOM] Re: Non-constructive nature of probabilistic proofs
Timothy Y. Chow
tchow at alum.mit.edu
Tue Nov 4 16:45:00 EST 2003
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
More information about the FOM
mailing list