I appreciate you providing your sage advice and knowledge. Your webpage is really good. It's amazing how much information there on your website. monopoly online is a great game to pass the time if you want to come over and play with me after a long day at work.

Most of the claimed proofs on the P = NP side listed at https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm are constructive.

@duck_master Makes sense I suppose, but I don’t expect that to have anything to do with the actual answer.

we today can go and write an algorithm that solves SAT in polynomial time if P=NP

@warty How?

@IsaacKing enumerate all algorithms and compose each with a solution checker. run in parallel, nth algorithm at 2^-n speed. if a polynomial algorithm exists, it will run in polynomial time just with a big constant, and we will know if any algorithm produces a solution thanks to the checkers. I guess to answer negatively you would need to know what polynomial the running time is

@warty I suppose you're right, but that's not realistically going to yield a constructive proof.

Also, does the algorithm have to be tractable? If someone constructs an O(n^1000) algorithm that solves an NP problem, is that sufficient?

@IsaacKing No, tractability doesn’t matter for resolution.

Does the algorithm have to actually appear in the very first publication about the proof? Or does it count if there's just a proof first, but constructing an algorithm from the proof is easy and someone else does it shortly afterwards?

@IsaacKing If there’s just a proof first, there’s just a proof first, so this would resolve NO.

@NcyRocks What if the paper that publishes the proof also includes an algorithm, but the algorithm isn't necessary for the proof? (i.e. they could have left the algorithm out and the proof would still have been just as valid.)

@IsaacKing I guess that'd count for YES.

@NcyRocks Why? The description seems to be saying that the algorithm must be a part of the proof.

Resolves YES if P is proven to equal NP with the construction of a polynomial-time algorithm for an NP-complete problem, NO if P=NP is proven some other way

"If P=NP is proven, will the first proof be constructive?"