FOM: Erdos Probabilistic Method: Logical Status?

[Alasdair Urquhart]

Robert Tragesser's interesting questions about the 
probabilistic method are most naturally phrased within
the context of classical computational complexity theory
and the proof theory of bounded arithmetic.  
The notion of "constructive" is usually left undefined
in the literature of combinatorics, but it can quite
naturally be explicated in terms of feasible algorithms.
For the sake of definiteness, let's say that we identify
"feasible" with "polynomial-time computable," though
other explications are possible.

To explain the points at issue, I think it's a good idea
to focus on a definite problem, the diagonal Ramsey numbers.
In 1947, in one of the earliest and still most striking applications
of the probabilistic method, Erdos showed that 
R(k,k) > 2^k.  The proof is amazingly simple, being
nothing more than an averaging argument (first moment method).
The best constructive lower bound for diagonal Ramsey numbers is
still that of Frankl and Wilson (1981), who show by deep methods
of extremal set theory that R(k,k) > k^(log k / 4 log log k).
(The construction is simple, the proof that it works is deep.)
There are some new constructive lower bounds for off-diagonal Ramsey numbers,
due to Alon and Pudlak (see http://citeseer.nj.nec.com/288200.html).

Clearly, there is a huge gap here, between the "constructive" and
"non-constructive" lower bounds.  How do we make the idea precise?
A reasonable suggestion would be to ask the following question:

	Is there a polynomial-time algorithm that, given the number 2^k
	in unary notation as input, outputs a graph on 2^k nodes
	that contains neither a k-clique, nor a k-anticlique?

The usual problems in computational complexity ask for feasible algorithms
to determine if certain configurations exist.  In this case,
however, we know that the configurations exist by a non-constructive
argument.  But is there a feasibly constructive existence proof?

A lot of the literature in the proof theory of bounded arithmetic
and the related area of propositional proof complexity can
be considered as a kind of feasible reverse mathematics.
A partial answer to Tragesser's question about the pigeonhole
principle is to be found in the literature of this area.
A good reference to start from is Jan Krajicek's book on
bounded arithmetic and propositional logic.

Alasdair Urquhart