5 ms·

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. It's also true that TSP is NP har

by tgflynn 13y ago

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. 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 ago
  Can you elaborate on this binary search? How do you get a proposed path to feed to your decision problem?
  - ColinWright 13y ago
    Roughly - 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 ago
      Removing 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 ago
        Sorry, 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 ago
    This 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 ago
That 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 ago
  The maximum is bounded by the number of edges times the maximum edge cost.
  - wolfgke 13y ago
    It 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 ago
      I 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 ago
        Not 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 ago
        No, 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.

by tgflynn 13y ago

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 ago
Can you elaborate on this binary search? How do you get a proposed path to feed to your decision problem?
- ColinWright 13y ago
  Roughly - 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 ago
    Removing 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 ago
      Sorry, 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 ago
  This 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 ago

That 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 ago
The maximum is bounded by the number of edges times the maximum edge cost.
- wolfgke 13y ago
  It 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 ago
    I 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 ago
      Not 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 ago
      No, 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.