the P vs NP problem attracts a lot of attention, not all of it desirable, for a wide variety of reasons. there are many P=NP claims eg on this widely cited list maintained by mathematician Woegeorgi, P vs NP page. also, intermittently there are hot questions on SE sites related to P vs NP (eg recently [2],[3]) below, & there is even a p-vs-np tag on both cs.se (p-vs-np) & tcs.se sites. the following is intended somewhat as a reference question.what are the basic/typical/common mistakes in P=NP claims?[1] How not to solve P=NP?, cs.se[2] P vs NP code exercise, codegolf.se[3] Analogs of P vs NP in the history of mathematics MO.se
what are the basic/typical/common mistakes in P=NP claims?
complexity theory;p vs np
Often, people claim to find a polytime algorithm for an NP-hard problem. A couple things could go wrong: The algorithm does not return a correct answer.The algorithm does not run in polytime.An example of the first mistake is Ted Swart's LP formulations for TSP. They were of poly-size (and so could be solved in polytime with any polytime LP algorithm), but the formulations were not tight. (More info here.)I have blogged about a particular case of the second mistake. The short story is that the proof of poly runtime solved a recurrence relation incorrectly.