Eight Signs A Claimed P≠NP Proof Is Wrong

Eight Signs A Claimed P≠NP Proof Is Wrong: "

As of this writing, Vinay Deolalikar still hasn’t retracted his P≠NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed.  The first reason is that we’re not going to separate k-SAT from much easier problems purely by looking at the structure of the solution space: see for example this comment by Ryan Williams.  The second reason is that, independently of the solution-space issue, Neil Immerman has identified critical flaws in the finite model theory part of the paper.

The researchers who actually studied Deolalikar’s paper, thought hard about it, and figured out in a matter of days why it doesn’t work deserve our undying gratitude (they certainly have mine!).  At the same time, if someday we have a P≠NP claim at this level several times per year—which I see as entirely possible—then it’s clear that the sort of heroic effort we saw over the last week isn’t going to scale.  And thus, several commenters wanted to know how someone as lazy as I am could nevertheless be so confident in predicting what would happen:

Would you enlighten us as to what was the PROCESS behind your quick and correct judgment? … Your quick nondeterministic hunch about the wrongness of all the 100 pages was quickly verified as correct. But how did you do it, confidently risking your reputation like a smooth poker player?

Scott Aaronsohn [sic], like Nassim Nicholas Taleb, you predicted the crash before it happened! You knew some fundamental weaknesses intuitively that the other Myron-Scholes Nobel prize winning economists (computer scientists) fell for!

While it pains me to say so, these commenters give me way too much credit.  The truth, as far as I can tell, is that many (most?) complexity theorists reached exactly the same conclusion as I did and just as quickly; it’s just that most (with some notable exceptions) were too cautious to say so in public.  Among those who did comment publicly, the tendency was to bend over backwards to give Deolalikar the benefit of the doubt—an approach that I considered taking as well, until I imagined some well-meaning economist or physicist reading my generous words and coming away with the impression that P≠NP must be either licked or else hanging by a thread, and at any rate couldn’t have been nearly as hard as all those computer scientists made it out to be.

So, in the future, how can you decide whether a claimed P≠NP proof is worth reading?  I’ll now let you in on my magic secrets (which turn out not to be magic or secret at all).

The thing not to do is to worry about the author’s credentials or background.  I say that not only for ethical reasons, but because there are too many cases in the history of mathematics where doing so led to catastrophic mistakes.  Fortunately, there’s something else you can do that’s almost as lazy: scan the manuscript, keeping a mental checklist for the eight warning signs below.

1. The author can’t immediately explain why the proof fails for 2SAT, XOR-SAT, or other slight variants of NP-complete problems that are known to be in P.  Historically, this has probably been the single most important ‘sanity check’ for claimed proofs of P≠NP: in fact, I’m pretty sure that every attempt I’ve ever seen has been refuted by it.
2. The proof doesn’t ‘know about’ all known techniques for polynomial-time algorithms, including dynamic programming, linear and semidefinite programming, and holographic algorithms.  This is related to sign 1, but is much more stringent.  Mulmuley’s GCT program is the only approach to P vs. NP I’ve seen that even has serious aspirations to ‘know about’ lots of nontrivial techniques for solving problems in P (at the least, matching and linear programming).  For me, that’s probably the single strongest argument in GCT’s favor.
3. The paper doesn’t prove any weaker results along the way: for example, P≠PSPACE, NEXP⊄P/poly, NP⊄TC⁰, permanent not equivalent to determinant by linear projections, SAT requires superlinear time … P vs. NP is a staggeringly hard problem, which one should think of as being dozens of steps beyond anything that we know how to prove today.  So then the question arises: forget steps 30 and 40, what about steps 1, 2, and 3?
4. Related to the previous sign, the proof doesn’t encompass the known lower bound results as special cases.  For example: where, inside this proof, are the known lower bounds against constant-depth circuits?  Where’s Razborov’s lower bound against monotone circuits?  Where’s Raz’s lower bound against multilinear formulas?  All these things (at least the uniform versions of them) are implied by P≠NP, so any proof of P≠NP should imply them as well.  Can we see more-or-less explicitly why it does so?
5. The paper lacks the traditional lemma-theorem-proof structure.  This sign was pointed out (in the context of Deolalikar’s paper) by Impagliazzo.  Say what you like about the lemma-theorem-proof structure, there are excellent reasons why it’s used—among them that, exactly like modular programming, it enormously speeds up the process of finding bugs.
6. The paper lacks a coherent overview, clearly explaining how and why it overcomes the barriers that foiled previous attempts.  Unlike most P≠NP papers, Deolalikar’s does have an informal overview (and he recently released a separate synopsis).  But reading the overview felt like reading Joseph Conrad’s Heart of Darkness: I’d reread the same paragraph over and over, because the words would evaporate before they could stick to my brain.  Of course, maybe that just means I was just too dense to understand the argument, but the fact that I couldn’t form a mental image of how the proof was supposed to work wasn’t a promising sign.
7. The proof hinges on subtle issues in descriptive complexity.  Before you reach for your axes: descriptive complexity is a beautiful part of TCS, full of juicy results and open problems, and I hope that someday it might even prove useful for attacking the great separation questions.  Experience has shown, however, that descriptive complexity also a powerful tool for fooling yourself into thinking you’ve proven things that you haven’t.  The reason for this seems to be that subtle differences in encoding schemes—for example, whether you do or don’t have an order relation—can correspond to huge differences in computational complexity.  As soon as I saw how heavily Deolalikar’s proof relied on descriptive complexity, I guessed that he probably made a mistake in applying the results from that field that characterize complexity classes like P in terms of first-order logic.  I’m almost embarrassed to relate this guess, given how little actual understanding went to it.  (Intellectual honesty does, however, compel me to point out that it was right.)
8. Already in the first draft, the author waxes philosophical about the meaning of his accomplishment, profusely thanks those who made it possible, etc.  He says things like, ‘confirmations have already started arriving.’  To me, this sort of overconfidence suggests a would-be P≠NP prover who hasn’t yet grasped the sheer number of mangled skeletons and severed heads that line his path.

You might wonder: if I had all these more-or-less articulable reasons for doubting Deolalikar’s proof, then why didn’t I just state my reasons in the first place, instead of placing a $200,000 wager?

Well, I probably should have stated the reasons.  I apologize for that.

The best one can say about the lazy alternative I chose is that it led to a somewhat-interesting socio-mathematical experiment.  By putting my life savings on the line, could I give the world a dramatic demonstration of just how high the stakes are with P vs. NP—that when computer scientists say this problem won’t be solved without a titanic advance in human knowledge, without overcoming obstacles like the ones mentioned in points 1-4 above, they’re not kidding? After such a demonstration, would more people get it?  Would they refrain from leaping out of their chairs at the next P vs. NP announcement?  Like Richard Dawkins staring unflinchingly at a steel pendulum swinging toward his face (which he knows has enough potential energy to almost hit him but not quite), would they remember that the only miracle in life is that there are no miracles, neither in mathematics nor in anything else?

I don’t know how well the experiment succeeded.

"

 

(Via Shtetl-Optimized.)