New Proof That P≠NP: Final Update - Almost Certainly not |

Written by Mike James | |||||

Friday, 01 September 2017 | |||||

Proofs that P=NP, and even for the less exciting and more likely P≠NP, abound. Most of them by enthusiasts who, usually, can be commended for their enthusiasm, but not so much for their proofs. However, the latest proof is by a respected complexity theorist and can't be dismissed in the usual way. Final Update: The paper has been withdrawn. ## Final Update 1 September.This is likely to be the final update because, apart from complexity theorists interested in knowing the details, the matter is essentially settled. On the 30th of August the paper was removed from ArXiv by its author, Professor Blum and an explanation added:
The URL for the home page is: http://theory.cs.uni-bonn.de/blum/blum.var But at the time of writing there is nothing relevant. So far the proof has been shown to be incorrect by a contradiction. I expect that something useful will come out of the work, even if it isn't a proof of P≠NP. This is how math and science work at their best. ## Update 2 August 26thScott Aaronson has posted, among other things, a summary of the current state of the examination of the proof.
He goes on to say:
He also gives a brief outline of why the proof must fail - because if it did work then you could apply it to a particular function, the Tardos function, and derive a contradiction that it wasn't in P when it provably is. Read the rest of his post for more details: HTTPS / Kurtz / eclipse / Charlottesville / Blum / P vs. NP ## Update 1We now have a new commentary on the paper, and the forthcoming eclipse (!) on Gödel’s Lost Letter and P=NP a must read blog on complexity theory written by Dick Lipton and Ken Regan at Computer Science at Georgia Tech. The general feeling expressed in the blog is that there are many vague sections in the proof and a general feeling of unease but not enough to say that it is wrong. One interesting comment on the proof is;
## More InformationA Solution of the P versus NP Problem Where is Norbert Blum's 2017 proof that P≠NPP≠NP being discussed? P vs NP Problem Clay Maths Institute ## Related ArticlesClassic Nintendo Games Are NP Hard Pancake flipping is hard - NP hard To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info More generally, even if the proof is flawed, does it contain new ideas that may be useful in the future? Blum’s proof claims a very strong lower bound of on the circuit complexity of whether a graph of edges has a clique of size . He gets a lower bound of for another function, where the tilde means up to factors of in the exponent. We would be excited if he had even proved that this function has a super-linear Boolean complexity. |
|||||

Last Updated ( Friday, 01 September 2017 ) |