Sunday, March 15, 2015
Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP?
When I was young and foolish and I heard that someone thinks they proven P=NP or P ≠ NP I would think Wow- maybe they did!. Then my adviser, who was on the FOCS committee, gave me a paper that claimed to resolve P vs NP! to review for FOCS. It was terrible. I got a became more skeptical.
When I was older and perhaps a byte less foolish I would think the following:
For P=NP proofs: I am sure it does not proof P=NP BUT maybe there are some nice ideas here that could be used to speed up some known algorithms in practice, or give some insights, or something. Could still be solid research (A type of research that Sheldon Cooper has disdain for, but I think is fine).
For P ≠ NP proofs: I am sure it does not prove P ≠ NP BUT maybe there are some nice ideas here, perhaps a `if BLAH than P ≠ NP', perhaps an nlog^* lower bound on something in some restricted model'.
Since I've joined this blog I've been emailed some proofs that claim to resolve P vs NP (I also get some proofs in Ramsey Theory, which probably saves Graham/Rothchild/Spencer some time since cranks might bother me instead of them). These proofs fall into some categories:
P ≠ NP because there are all those possibilities to look through (or papers that are far less coherent than that but that's what it comes down to)
P=NP look at my code!
P=NP here is my (incoherent) approach. For example `first look for two variables that are quasi-related' What does `quasi-related' mean? They don't say.
Papers where I can't tell what they are saying. NO they are not saying independent of ZFC, I wish they were that coherent. Some say that its the wrong question, a point which could be argued intelligently but not by those who are writing such papers.
OKAY, so is there ANY value to these papers? Sadly looking over all of the papers I've gotten on P vs NP (in my mind- I didn't save them --should I have?) the answer is an empirical NO. Why not? I'll tell you why not by way of counter-example:
Very early on, before most people know about FPT, I met Mike Fellows at a conference and he told me about the Graph Minor Theorem and Vertex Cover. It was fascinating. Did he say `I've solved P vs NP' Of course not. He knew better.
Taking Mike Sipers's Grad Theory course back in the 1980's he presented the recent result: DTIME(n) ≠ NTIME(n). Did Mike Sipser or the authors (Paul, Pippenger, Szemeredi, Trotter) claim that they had proven P vs NP? Of course not, they knew better
Think of the real advances made in theory. They are made by insiders, outsiders, people you've heard of, people you hadn't heard of before, but they were all made my people who... were pretty good and know stuff. YES, some are made by people who are not tainted by conventional thinking, but such people can still differentiate an informal argument from a proof, and they know that an alleged proof that resolves P vs NP needs to be checked quite carefully before bragging about it.
When the result that Monotone circuits have exponential lower bounds for some problems there was excitement that this may lead to a proof that P ≠ NP, however, nobody, literally nobody, claimed that these results proved P ≠ NP. They knew better.
So, roughly speaking, the people who claim they've resolved P vs NP either have a knowledge gap or can't see their own mistakes or something that makes their work unlikely to have value. One test for that is to ask if they retracted the proof once flaws have been exposed.
This is not universally true- I know of two people who claimed to have solved the problem who are pretty careful normally. I won't name names since my story might not be quite right, and because they of them retracted IMMEDIATELY after seeing the error. (When Lance proofread this post he guessed one of them,
so there just aren't that many careful people who claim to have resolved P vs NP.) And one of them got an obscure paper into an obscure journal out of their efforts.
I honestly don't know how careful Deolaikar is, nor do I know if anything of interest every came out of his work, or if has retracted it. If someone knows, please leave a comment.
I discuss Swart after the next paragraph.
I WELCOME counter-example! If you know of a claim to resolve P vs NP where the authors paper had something of value, please comment. The term of value means one of two things: there really was some theorem of interest OR there really were some ideas that were later turned into theorems (or in the case of P=NP turned into usable algorithms that worked well in practice).
One partial counter-example- Swarts claim that P=NP inspired OTHER papers that were good: Yannakakis's proof that Swart's approach could not work and some sequels that made Lance's list of best papers of the 2000's (see this post). I don't quite know how to count that.