Re:A proof P = NP was accidentally published in TOCT
by LatteLazy on Monday July 19, 2021 @05:36PM
(#27887522)
I don't think a proof that P=NP is the same as actually turning all NP problems into P problems. You could prove it's POSSIBLE to break all current security without actually breaking any of it.
[ Parent
| on HN ]
Re:A proof P = NP was accidentally published in TOCT
by dragontamer on Monday July 19, 2021 @05:57PM
(#27887726)
More importantly, if it turns out that P = NP through a O(n^1,000,000,000,000) algorithm, then you've proven P = NP but no one is breaking much security any time soon.
But even finding a O(n^big_number) (where big_number is a googleplex, or graham's number... or some other absurdity) would be a huge advancement in theoretical computer science.
Re:A proof P = NP was accidentally published in TOCT
by DrBenCarson on Monday July 19, 2021 @05:50PM
(#27887645)
Proving it’s possible is the hard part, though. Granted, if you did actually implement a P-time algorithm that would also do the former.
Re:A proof P = NP was accidentally published in TOCT
by nraynaud on Monday July 19, 2021 @05:42PM
(#27887587)
I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
Re:A proof P = NP was accidentally published in TOCT
by erik on Monday July 19, 2021 @05:52PM
(#27887669)
In theory a proof could show that such an algorithm must exist without producing the algorithm itself. Though that's not what this linked paper tries to do.
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?
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.