[FOM] What is a "non-constructive proof"?

[Joe Shipman]

A and B are excellent examples of the kind of nonconstructiveness I asked for in my 3rd category. But there is still a natural bound on the size of object that needs to be searched for (in the factorization case) or the algorithmic complexity (in the “hex” case, exponential time and space by working backwards from end positions).

My 2nd category guarantees a solution but with no bound, and my 1st category (worse still) guarantees finitely many (possibly 0) solutions with no way of knowing when to stop searching.

— JS

Sent from my iPhone

> On Feb 18, 2020, at 4:31 PM, Timothy Y. Chow <tchow at math.princeton.edu> wrote:
> 
> Joe Shipman wrote:
> 
>> (1) A theorem that certain equations have finitely many solutions, with no bound given that would allow one to exhaustively search for them
>> (2) A theorem that a certain equation has a solution, with no bound given, but a guarantee that searching will eventually find one
>> (3) A counting argument that an object with certain properties of a certain size must exist, which comes with an implicit exponential bound on the search but no efficient construction.
> 
> For (1), I can't think of any examples offhand that I would consider to be at the undergraduate level.
> 
> For (2) and (3), I'm not sure if these exactly meet your desiderata, but you could consider:
> 
> A. A strategy-stealing argument for a game such as Hex proves that there is a first-player win, but yields no efficient algorithm for finding a winning move.
> 
> B. A primality test can prove that a composite number is not prime but without giving an efficient algorithm for finding a factor.
> 
> C. A probabilistic argument can show that Ramsey graphs exist (graphs on n vertices with neither a clique nor an independent set of size 2 log_2 n) without giving an efficient algorithm for constructing them.
> 
> See also this MathOverflow question:
> 
> https://mathoverflow.net/questions/77906/proofs-of-parity-results-via-the-handshaking-lemma
> 
> Tim