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:
Comments:
The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage
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 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 1
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
A Solution of the P versus NP Problem by Norbert Blum, the current chair of the University of Bonn Computer Department, is a new paper in arXiv. It isn't clear if it has been submitted to a refereed journal, but this hasn't stopped people from starting to argue about it. What might surprise you, if you are not a mathematician, is how doubtful the whole theorem proof system actually is. You might suppose that a paper like this would be of immediate interest and authoritative comments would follow, but there are just too many crank proofs and checking takes time.
For example, Scott Aaronson, who wrote a summary of the whole controversy and is everyone's goto person for such issues, posted this update to completely unrelated blog post:
Unrelated Update: To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper 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: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.
The problem is made worse by the fact that there have been some flawed papers produced by people who should know what they are doing. It seems it is too easy to convince yourself that you have proved something important about the issue, even if you are an expert.
Of course, proving that P≠N is the least exciting option, even though it still qualifies for the million dollar Clay prize. It is the least exciting because it is what most computer scientists expect to be the case.
An NP problem is one that is difficult to solve, but easy to check if you are given a solution. For example, you are given a logical expression in 1000 variables and your task is to find a set of 0/1 values that makes the expression true. To find the solution you need to search through all the values which takes a lot of time, but if I give you a proposed solution it is trivial to verify that it is or is not the solution - simply plug the values into the expression and see if it is true.
Another example is factoring. If I give you a big number and ask for its prime factors, then the only way you can find a solution is to search for divisors and this takes a lot of time. If I give you a list of the divisors you can check it in no time at all because you just divide the number by each one in turn.
What is tantalising about these NP problems is the ease of checking a solution. It seems to make the solution much closer than the search for it suggests. This leads some people to think that NP problems aren't really as hard as they seem and certainly they seem not to be as hard as problems that have solutions that are difficult to find and difficult to check.This drives people to prove that NP=P and shock everyone. Of course, given that most of our codes and online security mechanisms depend on NP problems being easy to check and hard to solve, this would also be a practical disaster.
More commonly it is held that NP problems are intrinsically difficult, it isn't that we just haven't found the algorithm. They may be quick to check, but it is a fact of nature that finding a solution in the first place is difficult.
This is what the latest paper seems to prove:
Berg and Ulfberg and Amano and Maruoka have used CNFDNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev’s function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P ≠ NP.
At the moment the online discussion jury seems to be undecided. Some early objections to the proof have been withdrawn, but some others have been raised. There is a general skepticism that the paper is too easy to be true. If this is all it took we should have had a proof some time ago - but this is not a counter proof. It is still amazing that a proof cannot be pronounced good or bad in a short time - that such a thing is not possible almost goes against the very idea of a proof.
Watch this space for more news as the dissection proceeds.
The Eclipse Foundation’s IoT Working Group has released the results of its 2024 IoT Developer Survey. Industrial automation and automotive are now the leading industry sectors and connectivity is th [ ... ]
Amazon has released new services for AWS Lambda SnapStart, Amazon's performance optimization that aims to significantly improve the startup time for applications.
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 ofon the circuit complexity of whether a graph ofedges has a clique of size. He gets a lower bound offor another function, where the tilde means up to factors ofin the exponent. We would be excited if he had even proved that this function has a super-linear Boolean complexity.
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.
