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 pro or con: Single author. It's becoming rare for important new work to not have multiple authors, especially from professional academics. However, Andrew Wiles...
After skimming its interesting that the majority of the proofs in your list claim P equals NP. I would have guessed it would be more common for proofs to claim the opposite because P != NP makes sense intuitively. That being said it would certainly be more exciting if P did equal NP.
The funny thing is that all these "solutions" are implications but not proof, and one contrary demonstration would actually render them all irrelevant as far as I understand the theory of computational p v np time complexity
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
FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."
"At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you."
Aaronson has commented on this particular proof. He's, to say the least, skeptical, based on an observed polynomial circuit in section 7: http://www.scottaaronson.com/blog/?p=3389
Points number 6 and 10 may apply. I only skimmed the paper and may have missed the really interesting point, but to me the argument and method just looks too simple to have been missed by everyone for all the time. But I am also totally not an expert in the field.
Interesting that this is the second P!=NP proof from a University of Bonn researcher. Other one, by Mathias Hauptmann, is here: https://arxiv.org/abs/1602.04781
I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed.
I might not get too excited over this proof, either, until another member of the TCS community can vouch for it. There have been many serious-looking attempts at PvNP that turn out to have fundamental flaws.
Also interesting: if you look at the acknowledgements of Hauptmann's paper (at the end, just before references), he says, "I would like to thank Norbert Blum for carefully reading preliminary versions of the paper, for helpful remarks and discussions, for his guidance and patience and for being my mentor." This means Blum knew about this past attempt and presumably thought it correct enough to put on arXiv. I assume from the current paper that he has changed his mind since then.
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.
Just a half minute skim shows the author claims it passes the natural proof barrier but makes no claim about it being non-relativizing or non-algebraizing.
For those following along at home: this is important because we have a proof that relativizing wouldn't work. In this context, relativizing means relative to an oracle. For example, P^A means "just like a Turing machine would regularly recognize languages except this one has a magical oracle that can recognize A in one step". A can be arbitrarily complex, including NP-complete ones like 3SAT.
This is important because the Baker-Gill-Solovay theorem already demonstrates that there exist oracles A != B relative to which P^A = NP^A, but P^B != NP^B. This shows that the problem has contradictory relativizations, and hence can't be proven that way. This matters because it's a litmus test against quack proofs.
I don't think this is a problem here; the proof doesn't appear to be doing that.
I like the straightforward title. I know that it is politically correct to christen your paper solving e.g. the Poincare conjecture like e.g. "Ricci flow with surgery on three-manifolds", but all rules are there to be broken once.
I see a few typos in the wording of the paper (e.g., "spezify", "touchs", etc.). While this doesn't mean much, I would expect if the paper had gotten a fine-toothed comb review that these sorts of typos would have been caught. Moving back to the "not holding my breath" stance unless there start to be indications from experts in the field that the claims are holding up.
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 answer 5 and comparing it with your answer. So we can conclude "Problems that are easy to solve are easy to verify" In other words, P ⊆ NP.
_Now is the reverse true? Are problems that are easy to verify also easy to solve?_
Let me give you an example. Let us assume that the question is "Is 1053188576519689 prime?". You come back and tell me, "No it is not prime, it is divisible by 32,452,867".
1) It is easy to verify your solution. I can divide 1053188576519689 by 32,452,867 and verify that it is indeed divisible.
2) It is hard to solve the problem, I have to try out numbers from 2,3,...,sqrt(1053188576519689), which is quite painful. (Or maybe there is as yet undiscovered better algorithm). So it appears that problems that are easy to verify may not be easy to solve. Or it appears that NP ⊆ P is not true. In other words, it appears P != NP (because if P ⊆ NP and NP ⊆ P, P == NP).
NP problems have wide ranging applications in things like cryptography for example. Let us assume I have a hashing technique. It is easy to hash a document, but hard to reconstruct the document from the hash. Then this technique can be used in auctions where you do not trust the auctioneer. You publicly submit the hash of your bid before the deadline. You do not submit your bid itself, because you are afraid that the person handing out the contracts will reveal the number to his brother-in-law who will bid $1 more than you and win the contract. After the deadline is passed, you send your actual bid to the Auctioneer.
Now
1) Everyone can verify that the documents have not been altered (the hashes are posted publicly, each document can be hashed and compared with its publicly posted hash). So it is easy to verify that the documents have not been tampered with after the deadline.
2) Nobody can construct the document from the hash. So it is not easy to solve for the bid document given the hash. So everyone can post the hash publicly with confidence before the deadline.
If P != NP we can have this type of auctions. If P == NP then there is no difference between posting the hash publicly and posting the document publicly.
Scott Aaronson has done some really good write-ups about P-NP, including what it means and what avenues of proof are possible. I'd start here: http://www.scottaaronson.com/papers/pnp.pdf. It probably doesn't count as "ELI5", but it's something.
After skimming the paper, the methods used look quite basic. There seems to be no really deep new insight as far as I can tell. Let's see what experts will have to say.
If his proof is correct, he gets unending fame, millions in prize money.
If his proof is laughably flawed, he'll promptly be forgotten as one of the 100s who have been wrong before him.
If he consults his peers:
If his proof is correct, he may end up sharing credit, maybe they'll even publish his work quietly under their own name while he's still waiting for feedback. Maybe that is what we are reading now.
If his proof is laughably flawed, then they'll give him his feedback and only his peers, instead of the whole internet will laugh at him for a day, before it's all forgotten.
Seems like with any tiny chance of a correct proof, the dominant strategy is, by far, to publish without consulting your peers.
What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.
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 may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.
Kind of like proving that you can't solve the halting problem, it lets us put to rest the idea that you can reduce the complexity of NP problems to a deterministic polynomial solution. The collective brainpower can be used to solve other problems.
"To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the proof won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: the paper claims to give an exponential circuit lower bound for Andreev’s function, but that function as defined in Section 7 of the paper seems clearly to have a polynomial-size circuit, based on polynomial interpolation (thanks to Luca Trevisan for this observation). So I don’t see how this can possibly stand. Please just stop asking, and if the thing hasn’t been fully refuted by the end of the week, you can come back and tell me I was a closed-minded fool."
Say you wanted to let a computer search for a proof of P!=NP - which axioms would you start with and which rules to transform the axioms into additional valid statements?
As someone with an undergrad level knowledge of the problem can someone please outline the importance of this research. Is this research done in some bounded domain. From what I have read in the comments, there seems to be other papers which have also proved P!=NP. So what does this research add...Just curious, feel free to ignore this...
> From what I have read in the comments, there seems to be other papers which have also proved P!=NP.
None of those papers have been accepted as correct, the problem remains open.
There's a gazillion articles describing the context and importance, and I suggest you do a web search for something like "P vs NP and why it's important".
So at least according to this P != NP. I’ve always been skeptical of this just because if you find an efficient optimal algorithm the problem moves between the classes.
[+] [-] ajarmst|8 years ago|reply
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 pro or con: Single author. It's becoming rare for important new work to not have multiple authors, especially from professional academics. However, Andrew Wiles...
[+] [-] DominikPeters|8 years ago|reply
[+] [-] valine|8 years ago|reply
[+] [-] sova|8 years ago|reply
[+] [-] Tomte|8 years ago|reply
[+] [-] lisper|8 years ago|reply
[+] [-] mcguire|8 years ago|reply
Aaronson on writes very well.
[+] [-] 1ris|8 years ago|reply
- Written in Word
- Uses techniques just seem too wimpy for the problem at hand.
- Was published in a predatory journal
[+] [-] Sniffnoy|8 years ago|reply
[+] [-] jimbokun|8 years ago|reply
So there's your real answer.
[+] [-] ajarmst|8 years ago|reply
[+] [-] danbruc|8 years ago|reply
[+] [-] kwaugh|8 years ago|reply
[+] [-] EGreg|8 years ago|reply
[+] [-] ethan_g|8 years ago|reply
I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed.
I might not get too excited over this proof, either, until another member of the TCS community can vouch for it. There have been many serious-looking attempts at PvNP that turn out to have fundamental flaws.
[+] [-] ndl|8 years ago|reply
[+] [-] alderz|8 years ago|reply
Sigma_2^p != NP as far as I know and after a brief skimming the paper does not mention P != NP.
Edit: the paper does indeed mention P != NP in the form of P != Sigma_2^p => P != Sigma_1^p = NP. Please disregard my comment.
[+] [-] jjgreen|8 years ago|reply
[+] [-] yifanlu|8 years ago|reply
[+] [-] lvh|8 years ago|reply
This is important because the Baker-Gill-Solovay theorem already demonstrates that there exist oracles A != B relative to which P^A = NP^A, but P^B != NP^B. This shows that the problem has contradictory relativizations, and hence can't be proven that way. This matters because it's a litmus test against quack proofs.
I don't think this is a problem here; the proof doesn't appear to be doing that.
[+] [-] ethan_g|8 years ago|reply
[+] [-] atemerev|8 years ago|reply
I wish the author best of luck.
[+] [-] mathgenius|8 years ago|reply
https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum...
[+] [-] rickbradley|8 years ago|reply
[+] [-] RSchaeffer|8 years ago|reply
[+] [-] teton_ferb|8 years ago|reply
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 answer 5 and comparing it with your answer. So we can conclude "Problems that are easy to solve are easy to verify" In other words, P ⊆ NP.
_Now is the reverse true? Are problems that are easy to verify also easy to solve?_
Let me give you an example. Let us assume that the question is "Is 1053188576519689 prime?". You come back and tell me, "No it is not prime, it is divisible by 32,452,867".
1) It is easy to verify your solution. I can divide 1053188576519689 by 32,452,867 and verify that it is indeed divisible. 2) It is hard to solve the problem, I have to try out numbers from 2,3,...,sqrt(1053188576519689), which is quite painful. (Or maybe there is as yet undiscovered better algorithm). So it appears that problems that are easy to verify may not be easy to solve. Or it appears that NP ⊆ P is not true. In other words, it appears P != NP (because if P ⊆ NP and NP ⊆ P, P == NP).
NP problems have wide ranging applications in things like cryptography for example. Let us assume I have a hashing technique. It is easy to hash a document, but hard to reconstruct the document from the hash. Then this technique can be used in auctions where you do not trust the auctioneer. You publicly submit the hash of your bid before the deadline. You do not submit your bid itself, because you are afraid that the person handing out the contracts will reveal the number to his brother-in-law who will bid $1 more than you and win the contract. After the deadline is passed, you send your actual bid to the Auctioneer.
Now 1) Everyone can verify that the documents have not been altered (the hashes are posted publicly, each document can be hashed and compared with its publicly posted hash). So it is easy to verify that the documents have not been tampered with after the deadline.
2) Nobody can construct the document from the hash. So it is not easy to solve for the bid document given the hash. So everyone can post the hash publicly with confidence before the deadline.
If P != NP we can have this type of auctions. If P == NP then there is no difference between posting the hash publicly and posting the document publicly.
[+] [-] Analemma_|8 years ago|reply
[+] [-] QML|8 years ago|reply
[+] [-] jjgreen|8 years ago|reply
[+] [-] danbruc|8 years ago|reply
[+] [-] ckugblenu|8 years ago|reply
[+] [-] nabla9|8 years ago|reply
Showing the draft to few colleagues to see if they can spot mistakes before 'shaking the world' is probably a good idea.
[+] [-] sean2|8 years ago|reply
If he publishes without consulting peers:
If he consults his peers: Seems like with any tiny chance of a correct proof, the dominant strategy is, by far, to publish without consulting your peers.[+] [-] choxi|8 years ago|reply
[+] [-] zolthrowaway|8 years ago|reply
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 may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.
[+] [-] bottombutton|8 years ago|reply
[+] [-] ajarmst|8 years ago|reply
"To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the proof won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: the paper claims to give an exponential circuit lower bound for Andreev’s function, but that function as defined in Section 7 of the paper seems clearly to have a polynomial-size circuit, based on polynomial interpolation (thanks to Luca Trevisan for this observation). So I don’t see how this can possibly stand. Please just stop asking, and if the thing hasn’t been fully refuted by the end of the week, you can come back and tell me I was a closed-minded fool."
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] TekMol|8 years ago|reply
[+] [-] fazkan|8 years ago|reply
[+] [-] CarolineW|8 years ago|reply
None of those papers have been accepted as correct, the problem remains open.
There's a gazillion articles describing the context and importance, and I suggest you do a web search for something like "P vs NP and why it's important".
Here's one: http://www.scottaaronson.com/blog/?p=459
HN discussion: https://news.ycombinator.com/item?id=1605415
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] andy_ppp|8 years ago|reply
[+] [-] spiznnx|8 years ago|reply
This hasn't ever happened.
You can prove an algorithm is in NP-hard by reducing another NP-hard problem to it. You can prove an algorithm is in P by showing the algorithm.
If you find and efficient algorithm to a problem in NP-hard, you show P == NP. No one has ever done this.
P != NP is considered by many to be most likely true.