1
$\begingroup$

How can TSP be an NP-optimization problem ?

The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and that the size of each $s \in S_\Pi(I)$ is polynomial bounded in $|I|$, where $|I|$ denote the size of $I$.

However, in the case of TSP an instance will be encoded using $n^2$ bits, where $n$ is the number of vertices in the instance graph, using the adjacency matrix representation.

But there are $n!$ feasible solutions ? In order to encode these one must use $n! \setminus 2^n$ bits. This number increase as $n$ increase, but $p(|I|)$ is fixed ?

How I overseen something ?

$\endgroup$
  • $\begingroup$ "The size of each $s \in S_{\Pi}(I)$ is polynomially bounded", not the number of solutions. $\endgroup$ – megas Mar 14 '15 at 17:48
  • $\begingroup$ But how should I encode $s$ so that I can represent each feasible solution using $p(|I|)$ bits ? Since there are $n!$ possibilities for $s$, I need to use at least $n! \setminus 2^n$ bits, right ? $\endgroup$ – Shuzheng Mar 14 '15 at 17:58
  • $\begingroup$ I noticed that detail in the question and I was about to answer. A solution in the TSP problem is a sequence of vertices, right? How many bits do you need for that? $\endgroup$ – megas Mar 14 '15 at 18:00
  • $\begingroup$ There are $n!$ sequences, so I need to use at least $n! \setminus 2^n$ bits ? $\endgroup$ – Shuzheng Mar 14 '15 at 18:01
  • $\begingroup$ You need $n \log n $ bits to encode all permutations of vertices: $n$ vertices each labeled with $\log{n}$ bits. This indeed grows with $n$. What exactly is the size of the instance $I$? $\endgroup$ – megas Mar 14 '15 at 18:08
2
$\begingroup$

A solution in the TSP problem is a sequence of $n$ vertices. Consider a labeling $1,\dots, n$ of the $n$ vertices. We need $O(\log{n})$ bits to encode the label of each vertex. Then, any sequence of $n$ vertices can be described by $O(n\log{n})$ bits; the concatenation of $n$ vertex labels. Hence, any solution $s$ of the TSP can be described by a number of bits that is polynomial in $n$.

The size of the instance $I$ is also polynomial in the number of vertices $n$, as noted in the original question.

$\endgroup$

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.