  The $k$-Opt algorithm is a local search algorithm for the Traveling Salesman
Problem. Starting with an initial tour, it iteratively replaces at most $k$
edges in the tour with the same number of edges to obtain a better tour.
Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the $k$-Opt
neighborhood is complete for the class PLS (polynomial time local search) and
that the $k$-Opt algorithm can have exponential running time for any pivot
rule. However, his proof requires $k \gg 1000$ and has a substantial gap. We
show the two properties above for a much smaller value of $k$, addressing an
open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular,
we prove the PLS-completeness for $k \geq 17$ and the exponential running time
for $k \geq 5$.
