# How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

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 ?

• "The size of each $s \in S_{\Pi}(I)$ is polynomially bounded", not the number of solutions. Commented Mar 14, 2015 at 17:48
• 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 ? Commented Mar 14, 2015 at 17:58
• 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? Commented Mar 14, 2015 at 18:00
• There are $n!$ sequences, so I need to use at least $n! \setminus 2^n$ bits ? Commented Mar 14, 2015 at 18:01
• 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$? Commented Mar 14, 2015 at 18:08

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.