|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:
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 26th
Scott Aaronson has posted, among other things, a summary of the current state of the examination of the proof.
".., it’s only intellectual honesty that compels me to report that, by about Friday of last week—i.e., exactly on my predicted schedule—a clear consensus had developed among experts that Blum’s P≠NP proof was irreparably flawed, and the consensus has stood since that time."
He goes on to say:
"The background to Blum’s attempt, the counterexample that shows the proof has to fail somewhere, and the specifics of what appears to go wrong have already been covered at length elsewhere: see especially Luca’s post, Dick Lipton’s post, John Baez’s post, and the CS Theory StackExchange thread."
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
We 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 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.
End of Update
or email your comment to: firstname.lastname@example.org
|Last Updated ( Friday, 01 September 2017 )|