2
$\begingroup$

Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better.

Question for TSP-decision problem: Given n cities and a tour from length $k$. The traveller starts at an arbitrary city, visits every other city just once and returns to the starting point. Does a tour from length $\leq{} k$ exist?

Let's first check whether the TSP is in NP:

A proof is given. Proof in this case is a tour. For it to be in NP, we must be able to verify this proof with a deterministic algorithm in polynomial time. So first we have to check, whether every city is only visited once. This can be done at most in $O(n^2)$. Next we need to calculate the distances and sum them up. This can be done as well at most in $O(n^2)$. The last step is to check whether the calculated length is $\leq{} k$. The hole process would require a polynomial time $\rightarrow 2 n^2 = O(n^2)$.

So the TSP-decision problem is in NP. What about the NP-hardness? We don't need to prove that, because Richard M. Karp proved that the Hamiltonian Circuit is NP-complete. The TSP is a special case of the Hamiltonian Circuit, therefore we know TSP must be NP-complete as well. NP-complete means = NP-hard and NP.

Is this possible with TSP-optimization problem?

Question for TSP-optimization: Given n cities and a tour from length $k$. A traveller starts at an arbitrary city and visits every other city just once and returns to the starting point. Is tour from length k the shortest tour? We can check in polynomial time, that every city is visited once. However we can't check whether $k$ is really the shortest tour, because we would have to check every other possible tour as well. That would mean $(n-1)!$ possible tours. And this would make the hole process above exponential.

So TSP-optimization problem is not in NP? Therefore it is not NP-complete, but NP-hard?

Anything wrong about my thoughts?

Improve this question
$\endgroup$
5
  • $\begingroup$ Duplicate? Or that? $\endgroup$
    – Raphael
    Commented Aug 20, 2017 at 18:55
  • $\begingroup$ I already saw them and they have to many formal/technical/mathematical definitions, which leads to my lack of understanding. I just need a plain explanation, maybe on an example (here TSP), because I'm totally a newbie to complexity theory. Actually I'm trying to understand it out of interest, because I came across the TSP, where I had to write a code which approximates a solution. However now I'm reading more and came across the complexity theory. @Raphael $\endgroup$
    – Meliss
    Commented Aug 20, 2017 at 19:20
  • 2
    $\begingroup$ Unfortunately, you will have to come to grips with formal definitions – that's the only way to really understand these concepts. $\endgroup$
    – Yuval Filmus
    Commented Aug 20, 2017 at 20:35
  • $\begingroup$ Yes. The way to get started is to grasp the basics, including formalism and mathematics. Worry about subtleties later. $\endgroup$
    – Raphael
    Commented Aug 20, 2017 at 21:52
  • $\begingroup$ The TSP is a special case of the Hamiltonian Circuit, therefore we know TSP must be NP-complete as well. -- I think you mean that Hamiltonian Circuit is a special case of TSP? $\endgroup$
    – user53923
    Commented Nov 9, 2017 at 10:33

2 Answers 2

Reset to default
1
$\begingroup$

Only decision problems can be NP-hard or NP-complete; these are problems for which the answer is either Yes or No.

Optimization problems have an optimal solution as an answer. The associated decision problem is, given an instance and a value, whether the the value of an optimal solution is as good or better than the given value.

When we say that an optimization problem is NP-hard, we mean that its associated decision problem is NP-hard; it is an abuse of terms. We could also say that an optimization problem is NP-complete if its associated decision problem is NP-complete.

The TSP optimization problem is, given a graph, find a TSP tour of shortest length. The associated decision problem is, given a graph and a value $k$, decide whether the shortest TSP tour has length at most $k$. These are different than the problems that you describe.

Sometimes we are interested in a weaker version of the optimization problem, namely, given an instance, find the value of an optimal solution. This is the perspective usually considered in the field of hardness of approximation, in which the goal is to show that it is NP-hard to even approximate the optimal value.

Improve this answer
$\endgroup$
12
  • 1
    $\begingroup$ Optimization problem can be rewritten as: is a cycle of length $k$ is optimal? This is decision problem and not known to be in $\mathsf{NP}$. $\endgroup$
    – rus9384
    Commented Aug 20, 2017 at 20:44
  • $\begingroup$ When people say optimization problem they usually mean other things. You can of course use the name to whatever you want to. Your problem is in $\Delta_2^P$, and is probably not in NP. In fact, I would guess that if it is in NP then the polynomial hierarchy collapses. $\endgroup$
    – Yuval Filmus
    Commented Aug 20, 2017 at 20:52
  • $\begingroup$ This is the difference between $NP$ and $P^{NP}$. Former can only choose optimal (1) value in 0-1 alphabet and latter can find optimum in the set of integer numbers (bounded by $O(2^n)$) of linked problems. $\endgroup$
    – rus9384
    Commented Aug 20, 2017 at 20:58
  • $\begingroup$ The latter is also a class of decision problems. Perhaps you're thinking of FP? $\endgroup$
    – Yuval Filmus
    Commented Aug 20, 2017 at 21:43
  • $\begingroup$ Yes, but then NP also should be changed by FNP as a machine that returns certificate. I don't think there is any other difference in definition of these classes. $\endgroup$
    – rus9384
    Commented Aug 20, 2017 at 21:51
-2
$\begingroup$

I would like to point out that the TSP optimization problem returns a Minimum length Hamiltonian-Cycle for the graph. Now, our job to prove this problem is in NP class invloves

Checking whether the Minimum length falls within a range.

Now this range is calculated by adding the weight of n-1 number of edges in increasingly sorted order for the minimum bound and decreasingly sorted order for the maximum bound (This maximum or minimum values are not necessarily cycle-lengths). This whole checking process can be done in polynomial time. Hence, TSP optimization problem also lies in NP class.

If anyone thinks that the way of proving this problem to be NP class isn't correct, I would also point out what Raphael originally posted :

However we can't check whether k is really the shortest tour, because we would have to check every other possible tour as well. That would mean (n-1)! possible tours. And this would make the hole process above exponential.

This problem itself is similar to the TSP problem and thus is not what we want to look for.

P.S. Please correct me if I'm wrong anywhere !

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm sorry, but this is completely wrong. The TSP optimization problem is not in NP for the simple reason that it is an optimization problem, whereas NP is a class of decision problems. Your test of "checking whether the minimum length falls within a range" has nothing to do with the definition of NP. It is true that the minimum-weight cycle can't have weight less than the sum of the $n$ lightest edges or more than the sum of the $n$ heaviest edges, that does nothing to help you if the claimed solution doesn't violate those trivial bounds. $\endgroup$
    – David Richerby
    Commented Nov 8, 2017 at 10:47
  • $\begingroup$ For example, suppose I tell you that the shortest Hamiltonian tour of the 20 largest cities in India has length 150km. Obviously, that's wrong. Likewise, if I say it has length 150,000,000km, that's obviously wrong. But what if I claim that it has length 7,500km? How are you going to check that claim in polynomial time? $\endgroup$
    – David Richerby
    Commented Nov 8, 2017 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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