We show that certain ways of solving some combinatorial optimization problems can be understood as using query planes to divide the space of problem instances into polyhedra that could fit into those that characterize the problem's various solutions. This viewpoint naturally leads to a splinter-proneness property that is then shown to be responsible for the hardness of the concerned problem. We conjecture that the $NP$-equivalent traveling salesman problem (TSP) has this property and hence is hard to solve to a certain extent.
翻译:我们展示了解决某些组合优化问题的某些方法可以理解为使用查询平面将问题实例的空间划分为可适应于问题各种解的特征多面体的空间。这一观点自然地引出了一个分叉易感性的特性,由此证明了该问题的难度。我们猜想$NP$等价的旅行商问题(TSP)具有这种特性,因此难以解决到一定程度。