The k-Opt algorithm for the traveling salesman problem works by local search: examine the current tour, find k edges whose replacement would shorten it, and swap. Repeat until no k-edge improvement exists. The algorithm terminates at a local optimum, but reaching that optimum can take exponentially many steps.
Note (2026-11-13; read against the paper's full text): the paper proves PLS-completeness of k-Opt for every k at least 15 (by a new reduction from bounded-degree Max-Cut), and it recovers that Krentel estimated his own proof gave a k between 1,000 and 10,000 and that filling in his missing details gave 14,208. It does not settle k below 15, including the k = 2 and 3 the essay calls the practical versions; that remains open in this paper. Hardness for all k from 15 upward is the opposite of a threshold where richer neighborhoods 'stop helping', and the essay's remark that hardness is not monotone in the neighborhood size is the essay's own, not the paper's. The paper also says its earlier conference version had the threshold at 17, and that an exponential-time result for k at least 3 appeared later in other work.
PLS-completeness captures this: a problem is PLS-complete if finding a local optimum is as hard as any polynomial-time local search problem. For k-Opt, PLS-completeness was known only for astronomically large k — over 1,000. The practical versions of the algorithm use k = 2 or k = 3.
The new result (arXiv:2603.11270) drops the threshold to k ≥ 15. This is the first rigorous proof of PLS-completeness for k-Opt, and it closes a gap that had been open since Monien, Dumrauf, and Tscheuschner posed the question. The result holds for both general and metric TSP.
The structural insight: the hardness of local search is not monotone in the neighborhood size the way one might expect. Larger neighborhoods make each step more expensive but potentially reduce the number of steps. PLS-completeness at k = 15 means the combinatorial complexity of the improvement graph is already rich enough to encode arbitrary local search problems — the threshold where “richer neighborhoods” stops helping and starts encoding hardness is much lower than previously known.