2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 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 '19 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 '19 at 15:06
5
$\begingroup$

Yes, you are right: there are plenty of other possible algorithms the author ignores. Briefly, the author claims that the $\Theta^*(2^n)$ dynamic programming approach in the paper is nessecary to solve TSP. However, he completely ignores 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 his argument. Clearly, even if the claim of the author is correct, he has not proven it.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ First of all the author is a male, one person, and is offended by the use of the "they" pronoun. Second of all, this answer is wrong, because it ignores the fact that the P vs NP problem is a problem about the worst case running time of an algorithm, not about whether there exist algorithms that can efficiently solve special instances of a particular NP complete problem. The fact that there are special instances of the TSP that can be efficiently solved is irrelevant. $\endgroup$ – Craig Feinstein Dec 12 '19 at 4:19
  • $\begingroup$ Second of all, the argument in the paper is not valid for the simple example in this answer, since in this case the recursive formula could be simplified to $(n-1)\cdot X$. But in the general case, the recursive formula cannot be simplified, so there is no problem. $\endgroup$ – Craig Feinstein Dec 12 '19 at 6:08
  • 6
    $\begingroup$ @CraigFeinstein The claim that the recursive formula cannot be simplified in the general case needs proof. The point of my example is to show why this claim needs proof: it is false in a restricted case, but the argument applies equally well to the general case as to the restricted case. This means the argument is incomplete or wrong. $\endgroup$ – Discrete lizard♦ Dec 12 '19 at 7:24
  • 1
    $\begingroup$ "There are two possible ways to simplify the recursive formula in the paper" that you can think of. $\endgroup$ – Tassle Dec 12 '19 at 20:14
  • 1
    $\begingroup$ @CraigFeinstein if you unpack the $\Delta$ you’ll see that there are ways to simplify. The main problem with your argument is that it completely ignores structure of TSP. You could prove along the same lines that Assignment Problem is exponentially hard, but it actually has polytime algorithms. $\endgroup$ – Dmitri Urbanowicz Dec 13 '19 at 5:40
1
$\begingroup$

From the article: "This lower bound is confirmed by the fact that the fastest known deterministic and exact algorithm which solves the Traveling Salesman Problem was first pub- lished in 1962 and has a running-time of Θ∗(2n)".

I very much doubt that anything found in 1962 is the fastest known algorithm for anything. It's a very strong claim with absolutely no evidence. As far as I know, there are algorithms that solve problems with 10 thousands of nodes. So this statement is unacceptable to prove the claim.

But if you prove that the currently fastest known algorithm from 2019 doesn't run in polynomial time, that still doesn't prove anything. Because for P ≠ NP to be true, not only known algorithms but any algorithms must run in non-polynomial time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It is an amazing fact that the fastest known deterministic and exact algorithm which solves the TSP was first published in 1962. This is confirmed by Woeginger's paper cited in the Feinstein paper. While that paper was written in 2003, no algorithm since then has been found to beat Held and Karp's algorithm for TSP. It there were, you would have heard about it. $\endgroup$ – Craig Feinstein Dec 12 '19 at 17:22
  • 1
    $\begingroup$ It seems you don't get it. It doesn't matter what known algorithms do. To prove that P ≠ NP, you have to prove that no algorithms, including algorithms that you would never dream of, can solve the problem in polynomial time. $\endgroup$ – gnasher729 Dec 13 '19 at 2:12
  • $\begingroup$ gnasher729, you have not found any holes in the proof. $\endgroup$ – Craig Feinstein Dec 13 '19 at 2:23
  • $\begingroup$ @CraigFeinstein The onus is on you to prove that no "surprising algorithms" exist; we don't need to find one to discard your argument, you have to prove that none exists yourself. (Note that a similar naive argument would imply that PRIMES is not in P ...) $\endgroup$ – Noah Schweber Dec 13 '19 at 17:32
  • $\begingroup$ @NoahSchweber I did prove it. The onus is now on you to prove that there exists a hole in the proof, if that is indeed your claim. As for proving that no "surprising algorithms" exist, my proof already does this. $\endgroup$ – Craig Feinstein Dec 13 '19 at 18:15

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.