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

Timothy Y. Chow tchow at math.princeton.edu
Wed Feb 19 12:00:25 EST 2020


On Wed, 19 Feb 2020, Joe Shipman wrote:
> 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.

This isn't a perfect example, but how about Levin universal search?  We 
can explicitly write down an algorithm A with the following property:

   (*)  If P = NP then A solves SAT in polynomial time.

There is no bound on the degree of the polynomial.  But in some sense we 
are "guaranteed a solution."  Of course the big catch is that we don't 
know that P = NP.

Tim


More information about the FOM mailing list