Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?
Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve ? (P)". Note that the reverse is obviously true : problems that are easy to solve are also easy to verify . Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the…
I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.
> serious cahunas I think you mean "cojones" (which btw is a very rude word in Spanish). A kahuna is a kind of Hawai'ian shaman.
I'm sitting here chuckling to myself about the "why not both?" possibilities.
> Nobody's really interested in a proof that P != NP. This is not the case. In my day job I need to worry about what happens if ECDSA is broken. One way that can happen is quantum computation -- but that has a relatively transparent development timeline we can plan for. The other way in which ECDSA could be broken is if P==NP and the discrete log problem can be transformed in polynomial time into another polynomial t…
Knowing P?NP does not imply much in practice unless the answer precisely bounds complexity. N^(N*1e-100) is exponential yet very practical while N^1e100 is polynomial yet is useless in this Universe.
This is definitely one of those "I'm going to wait for the peer review" claims, but it is pretty exciting. Pros: The author is not a dilettante, and is actively researching in the area ( http://theory.cs.uni-bonn.de/blum/Forschung/forsch.var ) Cons: It's not my area, but I was expecting something a little more novel for a solution to P?NP. This almost seems too simple (it might almost fit in a margin...). Could be pr…
The paper looks like it is 38 pages and builds on other work. That doesn't seem too simple to me.
Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304
Proof for the Gaussian correlation inequality was - Written in Word - Uses techniques just seem too wimpy for the problem at hand. - Was published in a predatory journal
Hence why Scott explicitly takes time to address that there will surely be outliers on both ends
Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304
Proof for the Gaussian correlation inequality was - Written in Word - Uses techniques just seem too wimpy for the problem at hand. - Was published in a predatory journal
The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…
I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.
This is correct. And, in fact, P=NP.
However, while P=NP, the algorithm (oracle) resides on the other side of the event horizon. This is called the MAD paradox.