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?

  • 1
    $\begingroup$ I'm sorry but you're effectively asking us to peer-review the given article, which isn't what this site is for. We deal with short, focused, self-contained questions that aren't going to require hours of work. The manuscript you cite makes no formal argument so there isn't really anything to dispute. $\endgroup$ – David Richerby Apr 30 at 14:50
  • $\begingroup$ @DavidRicherby To be fair, the 'paper' is really short. I think the main argument can be summarized. If that is done, I think the question is ok. Anyway, while it might be interesting to pinpoint the flaw, I wouldn't really trust this result, especially given this authors' further bibliography: arxiv.org/search/… . $\endgroup$ – Discrete lizard Apr 30 at 15:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.