News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by allochthon on Monday July 19, 2021 @05:26PM (#27887436)
Can someone in the know unpack what's going on here for a less-informed audience? I know vaguely about the outstanding question of whether P = NP, and how it's generally thought that P is not equal to NP. But beyond that most of the context here is unknown to me.
Re:A proof P = NP was accidentally published in TOCT by throwaway81523 on Monday July 19, 2021 @05:55PM (#27887691)
1. P vs NP is a famous open CS problem, which (like Fermat's last theorem back in the day) attracts a huge number of crackpots purporting to have proofs one way or the other. There is a million dollar reward (Clay Millenium Prize) for the first correct proof, but obviously it has not been paid out so far.

2. There are also some attempts by legitimate researchers (non-crackpot) but that also turn out to be wrong. You can see some examples of wrong proofs (most crackpot, some not) here: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm

3. Someone submitted yet another "proof" to TOCT (legit journal). The journal presumably gets those all the time. They took a quick look at the manuscript and rejected it as usual. They are used to that.

4. Because of some kind of clerical error, the manuscript somehow found its way into TOCT's publication queue even though it had been rejected. This provoked the obvious WTF from people who saw it.

5. There are now some tweet threads etc. clearing up the confusion. It's just another bogus P vs NP proof, like the 100s that have already appeared. Nothing to write home about. This has been going on for decades.

Re:A proof P = NP was accidentally published in TOCT by cakoose on Monday July 19, 2021 @06:16PM (#27887928)
Whether P = NP is a long-standing problem. Like many long-standing problems, it's deceptively difficult, which results in many people incorrectly claiming they have solved it: https://www.scottaaronson.com/blog/?p=458

A lot of cryptography relies on NP problems being difficult to solve. If someone figures out a way to solve NP problems in polynomial time, they may keep that technique to themselves rather than publish it. The rest of us might only become aware of this after we see real-world crypto being broken.

In this particular case though, it was just another P = NP paper that was rejected, but accidentally got published.

Re:A proof P = NP was accidentally published in TOCT by paulddraper on Monday July 19, 2021 @09:09PM (#27889095)
Though if P = NP, the exponent could possibly very high, removing the practical effect.
Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @05:30PM (#27887475)
Are you looking for context regarding how this proof ended up in a prestigious academic journal (when the journal had already planned to reject it) or a more general overview of why any proof that P=NP will likely show up first not in an academic journal, but in a catastrophically massive security breach that lays bare all of the secret information from multiple organizations simultaneously?
Re:A proof P = NP was accidentally published in TOCT by allochthon on Monday July 19, 2021 @05:32PM (#27887491)
> a more general overview of why any proof that P=NP will likely show up first not in an academic journal, but in a catastrophically massive security breach that lays bare all of the secret information from multiple organizations simultaneously?

This is probably what I was looking for. Is there a good discussion of this topic?

Re:A proof P = NP was accidentally published in TOCT by herodotus on Monday July 19, 2021 @05:37PM (#27887534)
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.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:25PM (#27887991)
To very much over simplify:

Some problem are "easy", there is a way to solve even complex ones with a (relatively) small amount of effort. These are P.

Other problems have no known "easy" method and the solution to a given problem can only be determined by something like brute force, such as trying every possibility.