Let me be he last on the block to tell you that an alleged proof of P ≠ NP is out there. NOT posting on it would be absurd; however, I cannot do any better than what Richard Lipton already posted so I point you to his post.
So what are my uninformed views? If I was a betting man I would bet
that it won't pan out. I would bet that he proved something very interesting,
but not P ≠ NP. Why do I think this?
This is NOT based on the author who seems to be a person to be taken seriously.
Its just that the problem is so hard and we've made no progress
on it since... . Hmmm, when is the last time we made progress on it?
Parity not in constant depth? Other bounds on weak models?
Oracles? Natural Proofs? Something from Mulmuley's program?
Fagin's theorem connecting the problem to finite model theory
(which is used in the alleged proof)?
I would have thought we would make slow progress at first.
Not sure what type- Maybe SAT ∉ DTIME(nk) for small values
of k. Maybe something else.
Scott Aaronson apparently IS a betting man. See
on the problem.
I was going to go to the
Barriers in Computational Complexity II workshop.
If the proof is correct I hope Amtrak gives refunds.
Actually- looking over the schedule, much of it will still be relevant.
If the proof is CORRECT how will that change
what we teach? What we work on? Lance's book-for-the-layperson on
complexity theory? (I recently proofread a chapter on what the world
would be like if P=NP. He may have to remove it. Too bad, it was