Upper bounds on ATSP neighborhood size. (Q1406047)

We consider the Asymmetric Traveling Salesman Problem (ATSP) and use the definition of neighborhood by \textit{V. G. Deineko} and \textit{G. J. Woeginger} [Math. Program. 87, No. 3 (A), 519--542 (2000; Zbl 1043.90075)]. Let \(\mu(n)\) be the maximum cardinality of polynomial time searchable neighborhood for the ATSP on \(n\) vertices. Deineko and Woeginger conjectured that \(\mu(n)<\beta(n-1)!\) for any constant \(\beta>0\) provided P\(\not=\)NP. We prove that \(\mu(n)<\beta(n-k)!\) for any fixed integer \(k\geq 1\) and constant \(\beta>0\) provided NP is neither a subset of nor equal to P/poly, which (like P\(\not=\)NP) is believed to be true. We also give upper bounds for the size of an ATSP neighborhood depending on its search time.