On the several proofs about P and NP

Recently, I’ve found this nice web site that collects wrong proofs about P and NP relationship.


Currently there are 107 proofs. Probably, all of them are wrong (otherwise, probably we would know the guy) and the nice scoring function provided by Scott Aaranson here can be applied. This scoring function is the number of signs exhibited by the paper among the “Ten Signs a Claimed Mathematical Breakthrough is Wrong”.

  1. The authors don’t use TeX.
  2. The authors don’t understand the question.
  3. The approach seems to yield something much stronger and maybe even false (but the authors never discuss that).
  4. The approach conflicts with a known impossibility result (which the authors never mention).
  5. The authors themselves switch to weasel words by the end.
  6. The paper jumps into technicalities without presenting a new idea.
  7. The paper doesn’t build on (or in some cases even refer to) any previous work.
  8. The paper wastes lots of space on standard material.
  9. The paper waxes poetic about “practical consequences,” “deep philosophical implications,” etc.
  10. The techniques just seem too wimpy for the problem at hand.