Re:A proof P = NP was accidentally published in TOCT
by lovecg on Monday July 19, 2021 @06:05PM
(#27887802)
In fact if there was a non-constructive proof, we would already know a polynomial time algorithm for solving any NP problem: just iterate over all program lengths (from 1 to infinity) and then iterate over all programs of that length n, running each for n steps. If one of the guesses produces the correct answer (which it must if P = NP), we have a polynomial time algorithm! Wild, huh?
[ Parent
| on HN ]
Re:A proof P = NP was accidentally published in TOCT
by CaptainNegative on Monday July 19, 2021 @08:50PM
(#27888992)
This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative instances?
Re:A proof P = NP was accidentally published in TOCT
by lovecg on Monday July 19, 2021 @09:40PM
(#27889263)
I had to look this up since it’s been a while, but looks like no - this is not a full solution. It correctly accepts the positive instances in polynomial time but no algorithm is known that would fully decide all instances in polynomial time.