5 ms·

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

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.

shadowgovt 5y ago
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?
- allochthon 5y ago
  > 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?
  - herodotus 5y ago
    https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
- LatteLazy 5y ago
  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.
  - nraynaud 5y ago
    I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
    - csnweb 5y ago
      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.
    - erik 5y ago
      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.
      - lovecg 5y ago
        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?
        CaptainNegative 5y ago
        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?
        deleted 5y ago
        [deleted]
        lovecg 5y ago
        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.
throwaway81523 5y ago
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 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.
cakoose 5y ago
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 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.
- paulddraper 5y ago
  Though if P = NP, the exponent could possibly very high, removing the practical effect.
ineedasername 5y ago
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.

shadowgovt 5y ago

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?

allochthon 5y ago
> 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?
- herodotus 5y ago
  https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
LatteLazy 5y ago
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.
- nraynaud 5y ago
  I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
  - csnweb 5y ago
    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.
  - erik 5y ago
    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.
    - lovecg 5y ago
      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?
      - CaptainNegative 5y ago
        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?
        deleted 5y ago
        [deleted]
        lovecg 5y ago
        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.

throwaway81523 5y ago

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 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.

cakoose 5y ago

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 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.

paulddraper 5y ago
Though if P = NP, the exponent could possibly very high, removing the practical effect.

ineedasername 5y ago

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.