← All problems

All-exp property conjectures for local search

There exists a constant c>0c>0 and infinitely many Traveling Salesman Problem instances with nn cities, together with an initial Hamiltonian cycle T0T_0, such that every sequence of strictly improving 22-opt moves starting from T0T_0 and ending at a 22-opt local optimum has length at least 2cn2^{cn}.

References

Progress summary

Refreshed
Open · progress reported

A new unrefereed paper claims exponential-length improvement behavior in several local-search settings, but related cases remain open.

The conjectures ask when every improving local-search sequence must be exponentially long, rather than merely allowing one unlucky exponential sequence. The latest paper claims to settle three specified neighborhoods, including 22-opt TSP and two constraint-assignment cases.

Known results

  • For (2,2,r)(2,2,r)-MCA with flips, the all-exp property is proved for every r≥5r\geq 5; each constructed sequence has length 2n+3−72^{n+3}-7.
  • Every improving sequence for (2,2,2)(2,2,2)-MCA has length O(n2)O(n^2).
  • The r=3r=3 and r=4r=4 MCA cases have the weaker is-exp property, while all-exp remains open.
  • In TSP, 33-opt, 44-opt, and constant k≥5k\geq 5 are covered, while earlier work left 22-opt open.

October 2026 claimed advance

The paper claims infinitely many instances forcing every improving sequence to be exponential in three stated neighborhoods, with polynomial behavior after parameter reduction, thereby closing the advertised gaps. The claim is unverified; no independent assessment or identified error was found.

Current status (as of October 2026): the reported paper claims progress on 22-opt TSP and two assignment settings, but the broader family, including MCA cases r=3r=3 and r=4r=4, remains open and the new claims are unverified.

Sources

Solutions 0

No solutions have been posted yet.