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, N/A if P is proven to not equal NP or the problem is proven unsolvable somehow.
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.
@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
@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.)
@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