5 ms·
The TSP Isn't NP Complete
- tgflynn 13y agoIt's true that TSP is not NP complete because it is not in NP, because it is an optimization problem, not a decision problem. It's also true that TSP is NP hard. The simplest way to see this is that if you have solved a TSP you have also automatically solved the Hamiltonian Path problem for the corresponding graph and the Hamiltonian Path problem is known to be NP complete. What the op does not state and which is also very important to realize however is that TSP is also NP easy (and hence NP equivalent). In other words if you have an algorithm that can solve any NP complete problem in polynomial time (ie. P == NP) then you can use that algorithm to solve TSP (actually any finite optimization problem) in polynomial time. There is a sketch of a proof of this in one of my previous HN comments, but I'm pretty sure this is well known to complexity theorists, though there seems to be a fair amount of confusion about it on the web.
- ColinWright 13y ago> ... there seems to be a fair amount of confusion > about it on the web. There's a lot of confusion on the web about this. And while it's true that this is largely a small technical point, this is an area where small technical details can matter. > It's true that TSP is not NP complete because it is > not in NP, because it is an optimization problem, not > a decision problem. So we make it a decision problem by saying: "Is there a tour with cost less than K?" > ... if you have an algorithm that can solve any NP complete > problem in polynomial time (ie. P == NP) then you can use that > algorithm to solve TSP (actually any finite optimization problem) > in polynomial time. And, roughly speaking, you do that by binary searching on the cost of a solution. Set a lower limit of 0 and a random upper bound. Keep doubling that till you get a solution, then binary search.
- backlava 13y agoCan you elaborate on this binary search? How do you get a proposed path to feed to your decision problem?
- ColinWright 13y agoRoughly - and possibly with some errors ... It's not a path that we're feeding to the decision problem. The decision problem is when we have a graph with costs on the edges, and when someone says "Is there a solution of cost less than K?" We're assuming we have a way to answer that, and using that to get a solution to the optimization problem. We need to use that to find the best possible path. We start by finding the cost of the best possible path. Set k=1 and ask if there's a solution. If not, double K and ask again. Repeat until the answer is "Yes". Now you know there is a solution with cost in the range [0,K]. Set L=0 and U=K. Now do a binary search. Set K = L + (U-L)/2 and ask if there is a solution of cost K. If not, set L=K, if so then set U=K. Lather, rinse, repeat, until U-L is sufficiently small (1 if using integer weights - more care required otherwise). Now we know the optimum price. Remove an edge and see if there's still a solution. If there is, there's an optimal path without it. If not, the edge is in the optimal path. Repeat for all edges - some efficiencies can be made.
- ufo 13y agoRemoving one edge at a time won't work if there is a second, redundant, optimal path (every edge can be removed without altering the cost). I don't remember how you get around this but it shouldnt be too complicated...
- ColinWright 13y agoSorry, thought that was clear. If you remove an edge and find the cost doesn't change, don't put the edge back - carry on with the smaller graph.
- habitue 13y agoThis doesn't get you the path itself, it only gets you the length of the path. Think of it like this: the decision version question is: Is there a path of length k that hits all of the cities? The algorithm just has to answer yes/no, it doesn't have to give you the path itself. So you can use binary search to repeatedly ask whether there is a path with length less than k, and home in on the optimal length. You still don't know what the path is. We assume it would be difficult for the algorithm to make this determination without having actually discovered the path, but the problem doesn't require that it output any such path. Edit: This is wrong, ColinWright details how to get the actual path from just knowing the length
- gweinberg 13y agoThat doesn't seem at all obvious. It's pretty easy to prove that if you can answer whether or not there exists a path of length k in polynomial time then you can also find what that path is in polynomial time. They prove this in the Udacity course on complexity, which I found very interesting if not necessarily practically useful. But it seems to me that the possible values of k you can get grows exponentially with problem size, so you can't just use your decision algorithm on various kays to find the optimal k in polynomial time.
- ColinWright 13y agoThe maximum is bounded by the number of edges times the maximum edge cost.
- wolfgke 13y agoIt depends what encoding is used. If the edge costs are integers, this is true. Also such bounds are possible for rational costs (but you have to pay more attention). It gets a lot more difficult if non-rational edge weights are allowed.
- tgflynn 13y agoI think we're talking here about problems that can be fed to a digital computer and hence can be represented by a finite number of bits. I believe that would exclude non-rational weights.
- ColinWright 13y agoNot necessarily - quantities like, for example, sqrt(2) can be represented symbolically. So can quantities like e and pi. You can get around this by multiplying all edge costs by twice the number of edges divided by the smallest non-zero difference between costs, then rounding to integers. Or something similar.
- wolfgke 13y agoNo, it wouldn't exclude non-rational weights. Consider for example the field Q[sqrt{2}]. Any element a+b * sqrt{2} of it can be represented by two rational numbers a, b. Since any field extension is a vector space (in this case of dimension 2) the addition can be implemented trivially and the multiplication is (a1, a2) * (b1, b2) = (a1 * b1 + 2 * a2 * b2, a1 * b2 + a2 * b1) (#) A formula for inversion can easily be derived from (#). TLDR: there are different kinds of encoding than binary fractions.
- praptak 13y agoOnly decision problems can be NP-complete, other problems can only be NP-hard. The article is a horribly long winded rant over this nitpick. By the way, in the computational complexity community it is understood that if you say "TSP is NP Complete" you mean the decision version of the problem (is there a path shorter than K?) so nobody will bother to nitpick.
- anonymoushn 13y agoThe great thing is that the author doesn't seem to understand the distinction. He states in his update that he has a decision problem of finding the tour of minimal distance.
- deleted 13y ago[deleted]
- baddox 13y agoIsn't that decision problem also in NP? The traditional TSP decision problem is in NP, and it seems like you should be able to run that a polynomial number of times to solve his version.
- lvh 13y agoPerhaps the parent you're replying to means to say that the author doesn't appear to understand the distinction, because the wording being used doesn't make it a decision problem either. As long as we're nitpicking: decision problems have yes-or-no answers.
- slacka 13y agoI'm a little confused by this issue. According to Proof Wiki: "Because the Traveling Salesman problem is both NP and NP-hard the Traveling Salesman Problem is NP-complete." http://www.proofwiki.org/wiki/Traveling_Salesman_Problem_is_NP-complete#The_Traveling_Salesman_Problem_is_NP http://www.proofwiki.org/wiki/Traveling_Salesman_Problem_is_... Here's another site claiming it's not even in NP: http://www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunderstood-problem/ http://www.nomachetejuggling.com/2012/09/14/traveling-salesm... I'd love a clear explanation.
- praptak 13y agoNP is a class of decision problems - the solution has to be "yes" or "no". NP-complete problems are a subset of NP, so only decision problems can be NP-complete. TSP, the optimization version (what's the shortest path?) is an optimization problem therefore it is NP-hard, not NP-complete. TSP, the decision version (is there a path shorter than K?) is NP-complete.
- ColinWright 13y agoThere is a chance someone will correct me here, as I'm not an expert. Take this with a grain of salt. Or a handful. The second claim, that it's not in NP, is what this article is talking about. The optimization problem, as usually given, is not in NP because optimization problems are, by definition, not in NP. NP is for decision problems. That's why this is regarded by some as simply a technical nit-pick, but continues to be a major source of confusion for those unwilling or unable to reason in nit-picking detail. Certainly the decision problem "Is there a path of cost less than K?" is in NP, is NP-hard, and is therefore NP complete. This can then be leveraged up into a solution of the optimization problem. Use a lower bound of 0, an upper bound of #(E) * max{ e in E: cost(e) }, and do a binary search for the optimal cost. Does that help? With that information, you now need to re-read other sources.
- poke111 13y agoAS others have pointed out, this glosses over the distinction between the decision version of the problem and the optimization version. But the reason that it often gets glossed over is that it doesn't make much of a difference when it comes to the complexity class of the problem. In this case, the decision version of the problem is: Does a path exist shorter than K? But once you have a solution to that, you can use binary search to answer the optimization version of the problem: Find k such that there exists a path = k and no path < k. But when it comes to the question of verifiers the distinction does matter. because NP is only concerned with decision problems the OP is incorrect when he says that there's no poly time verifier, because there is one for the decision version of the problem, and that's all that matters.
- mydpy 13y agoThe title is misleading! I was so excited... and then abruptly disappointed. :(
- Pirate-of-SV 13y agoFirst I was petrified then I was relieved.
- arakawa 13y agoCats and dogs living together, mass hysteria, P=NP!
- tsahyt 13y agoThis might come across as quite harsh but the article could have been much shorter. NP is the class of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. A problem is called NP-hard when there is a polynomial-time reduction of 3-SAT to said problem. A problem is called NP-complete if it is both NP-hard and in NP. Since TSP is not a decision problem, it is not in NP, therefore it cannot be NP-complete. However, it is NP-hard. One can call this a minor nitpick. I still point it out every now and then when I hear people talking about such things. However, the really important thing is that we haven't found a way to solve NP-hard (and hence of course NP-complete) problems efficiently on a deterministic Turing machine (and hence computers as we can actually build them). An informal way of saying the same thing is "TSP is really really hard to solve". Either way, I'm always surprised at how many problems we encounter in our every day lives are actually NP-hard. Every decent puzzle game for instance is usually NP-hard. Goes to show that we don't really enjoy solving easy problems. EDIT: Of course there's also a decision version of TSP, as others have pointed out. This one is NP-complete of course.
- gizmo686 13y ago>Every decent puzzle game for instance is usually NP-hard. An interesting question is how many of these puzzles are NP-hard in practice. For example, Minesweeper in NP-hard. However, it is possible to solve many games of Minesweeper using simple deductive reasoning in polynomial time. This leads to the question of what is the average difficulty of a random game. My best attempt at formalizing this question is to imagine reducing every game with a polynomial time algorithm, then look at the complexity of the remaining games. The complexity of an original game of size n could be the average after you reduce all games of size n with your polynomial time algorithm. If this new complexity is sub exponential than it feels as if there is some sense in which the game is not often NP-hard. A more concrete example that comes to mind is Haskell's type inference. In general this type inference is NP-hard. However, there are algorithms that can solve it in polynomial time assuming a limit to nesting. Because no such limit actually exists, type inference is still exponential. But, because we never see arbitrarily deep nesting (except for contrived examples), this does not matter.
- 13y ago
- j2kun 13y agoThe OP's update is still incorrect. A problem in NP is a set of strings which a deciding Turing machine must accept (and it must reject all other strings). You cannot define a problem in NP by what the machine outputs, because for a decision problem you can only output a single bit. What the OP meant to say is that you can define TSP as a decision problem as follows: TSP = {<G, T> : G is a weighted graph, and T is a tour of minimal total weight} Then this achieves what we want: that deciding whether a given tour has minimal weight is NP-hard but not known to be in NP. You can also formulate the TSP problem as a decision problem this way: TSP = {<G, v>: G is a weighted graph with a tour of weight at most v}. This formulation is essentially equivalent to the first problem.
- taejo 13y ago> The problem is to find a circuit that goes through each city once and that ends where it starts. This in itself isn't diffcult. This is the Hamiltonian circuit problem, and is NP-complete. And the OP doesn't know what a decision problem is. Not the best person to be correcting other people's confusion.