[FOM] What is a "non-constructive proof"?
Timothy Y. Chow
tchow at math.princeton.edu
Tue Feb 18 15:07:09 EST 2020
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
More information about the FOM
mailing list