IP $\neq$ LP

And in case you might have heard otherwise, we still don't know about P and NP. There are some recently submitted papers (all of which are rather light on references) in the Computational Complexity section of the CS arXiv claiming that P and NP are the same thing, based on formulating the traveling salesman problem as a linear program. Of course, they all make the classic mistake of underestimating the importance of constraining the variables to be integers.

The traveling salesman problem (or the TSP, an abbreviation that reduces the running time of saying its name by a factor of 2) asks simply "What is the shortest journey that makes exactly one stop in every city on a list?" Lest you think this problem is hopelessly academic, peruse this description of a few of the applications of the TSP. And lest you think that this problem seems simple, consider that $1,000,000 rests on its resolution.

I suppose it's not too shocking that a glory-seeking Associate Professor and an unknown researcher (is he a graduate student? an employee of a call-center software company?) would throw their hats in the ring. Hopefully they will learn that integer programming (IP) is not the same thing as linear programming (LP).

Fortunately, R. Hofman has set the record straight. Now, will those other two fellows follow the directions for withdrawing a paper from the arXiv?

Update 11/3/2006: R. Hofman has composed a more general rebuttal to those authors that have used linear programming to claim that P=NP.