我们证明了旅行商问题（TSP）在 $2$‑opt 邻域下以及 $(3,2,2)$ 与 $(2,3,2)$ 最大约束分配（MCA）在翻转邻域下都满足 all‑exp 性质。all‑exp 性质指的是存在无限多实例，其初始解使得任意一条改进路径到局部最优的长度都是指数级的，从而每一次局部搜索都会耗时指数级。
对于 TSP，之前已知所有 $k$‑opt（$k\ge 3$）邻域都满足该性质；我们的结果补全了 $k=2$ 的情况，完整覆盖了所有 $k$‑opt。对于 $(p,q,r)$‑MCA，约束中最多包含 $p$ 个变量，每个变量最多出现在 $q$ 条约束中，且每个变量的取值域大小为 $r$。我们在 $(3,2,2)$ 与 $(2,3,2)$ 两个参数组合下证明了 all‑exp，且任意降低其中任意一个参数都会使所有改进翻转序列的长度降为多项式级，说明这两个结果是紧致的。
这三个结果都解决了长期悬而未决的开放问题。我们的证明基于一种统一的构造思路，揭示了这三类问题的局部搜索动力学之间的深层联系。
点评：该工作不仅填补了 TSP $2$‑opt 的理论空白，还精准界定了 MCA 参数空间中指数级搜索的边界，为理解局部搜索的极限行为提供了重要视角。