Norbert Blum Claims Proof of P≠NP
I’m working my way through this and will spend more time on it this weekend. Certainly I’m not qualified to judge, but there are some interesting bits to ponder.
A Solution of the P versus NP Problem
Fortnow, Lipton, Aaronson have all given a preliminary thumbs down without providing specifics. The next few days should be interesting. Chances are, of course, that it’ll get shot down.
For others not hip to the significance of this, here’s the tl;dr: Hard unsolved problem in computer science with important implications. Clay Mathematics Institute has offered $1,000,000 for solution. Many experts in the field believe that we’re a long way from a proof. Elderly—but highly regarded—theorist from Germany just lobbed this hand grenade into the discussion. Surprising in that it uses fairly conventional techniques and none of the newfangled tools that others are working on.
Update 2017-08-19: It’s looking bad for Blum. Alexander Razborov gives it a thumbs down.
Update 2017-09-01: Blum has acknowledged proof is incorrect. “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.” Look for statement, once released at http://theory.cs.uni-bonn.de/blum/.
GAME OVER