Monday, September 28, 2009

Debunking Proofs

One of the comments of the last post asked my (or someones) opinion on the proofs floating around that P=NP or P\ne NP.
  1. As a grad student I used to read these until I found the mistake or until it was incomprehensible, which was the more common experience. Now I do not even bother going to the website that claims to have the proof.
  2. I do not believe that someone whose knowledge of math is not very deep could possibly prove P\ne NP. Actually I do not believe anyone right now can prove P\ne NP. Any paper claiming such would have to begin with the answer to What are you using to get around the known barriers?
  3. A proof that P=NP is more plausible now, except that I believe that P\ne NP.
  4. Our time is limited. For most people in the field, debunking proofs is not worth our time. Once you've debunked a few and gotten into arguments with the authors you will agree.
  5. My most recent debunking was actually okay. I got a paper that claimed that he MIGHT have a proof that P\ne NP (I like the humbleness) and it was reasonably well written. I told him that everything he wrote about Ham Cycle applies to Eulerian Cycle as well, and hence the proof cannot work. He accepted that but also said he may get me a better draft later. He has not.
  6. I have found that debunking a proof that P\ne NP is usually easy: like the above, Eulerian Cycle may be a counterexample to the usual You have to go through all possibilities argument. Debunking a proof that P=NP may be harder since they can be just code. But I would like commentary on this--- what have you debunked and what to you find easy or hard to debunk?


  1. One of the comments of the last post asked my (or someones) opinion on the proofs floating around that P=NP or P\ne NP.

    You mean the paper that was written incoherently and wasn't even typed up in LaTeX? How did it get onto the ArXiv in the first place?

  2. Here's debunking for some code claiming P=NP:

  3. I think you can tell pretty fast whether a paper is a serious attempt or not. First of all the references, and then the style, tell very quickly if a paper is a bunch of nonsense or not.

  4. While I admit debunking flawed proofs is a boring task I cannot agree with a cavalier attitude towards proofs based solely on cosmetics like "references", "style" and whether it was written in LaTex or not (about time to bury that Jurassic monstrosity anyway...).

    May I point out that early Galois writings were ignored by respected referees (e.g. Poisson ) as being incomprehensible. Einstein's original 1905 paper on Relativity was deemed incomprehensible by many academic mummies of the age, until Max Planck gave it a thumbs up.

  5. As for not getting a response from the guy with #5, maybe he realized that it didn't work, and so gave it up (if so, that's cool).