News for hackers. Stuff that matters.
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.
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.
Re:A proof P = NP was accidentally published in TOCT by csnweb on Monday July 19, 2021 @05:51PM (#27887659)
There might be a possibility to prove that such an algorithm exists without knowing how the algorithm works exactly / being able to construct a runnable version of it.