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 ?