What's the flaw in the P != NP proof in the article “The Computational Complexity of the Traveling Salesman Problem”

Question

I am reading through some proof of inequality of P and NP but they are not accompanied by the flaws in the reasoning so I'm trying to find them by myself, just to see if I'm getting the logic right. As an example I am currently reading this (very short) proof that P != NP and for me the lack in the argomentation is the following: what the author writes about the algorithm is sacrosanct but does not deny in any way the possible existence of algorithms or tricks that would allow to solve the problem in polynomial time.

Am I right on this one?

Answer 1

Yes, you are right: there are plenty of other possible algorithms the author ignores. Briefly, they claim that the $\Theta^*(2^n)$ dynamic programming approach they consider is nessecary to solve TSP. However, they completely ignore any sort of structure that may or may not exist in TSP instances.

So, we can look at special cases of TSP where we do know that we have special structure to see their argument is insufficient. For a simple example, consider the graph class where there is exactly one tour with cost $X$ and all edges not part of this tour have cost $>X$. Clearly, we can find a tour in $O(|E|)$ by selecting all edges with cost $\le X$. Note that if the argument of this paper would apply to the general case, it would also apply to this one, so this is a contradiction with their argument. Clearly, even if the claim of the author is correct, they have not proven it.