论文标题
翻译不变的约束优化问题
Translationally Invariant Constraint Optimization Problems
论文作者
论文摘要
我们研究了2D网格上经典约束满意度问题的复杂性。具体而言，我们考虑了此类问题的功能版本的复杂性，并具有额外的限制：限制是翻译不变的，即变量位于2D网格的顶点，并且每个维度中的每对相邻变量之间的约束是相同的。因此，问题的唯一输入是网格的大小。这个问题等同于经典物理学中最有趣的问题之一，即计算网格上经典粒子系统的最低能量。我们提供了此问题复杂性的紧密表征，并证明了$ fp^{nexp} $的类已完成。 Gottesman和Irani（Focs 2009）还研究了经典的翻译不变的约束满意度问题。他们表明，确定最佳解决方案的成本是否低于给定阈值的问题是否为NEXP完成。因此，我们的结果是将其结果从决策版本加强到问题的功能版本。我们的结果也可以看作是Krentel 1988年著名结果的翻译不变设置的概括，表明SAT的功能版本已完成$ fp^{np} $。证明中的基本要素是研究问题的差异变体的复杂性。我们表明，对于$ n \ times n $ grid，将最佳分配的成本近似于$ω（n^{1/4}）$的添加误差之内是nexp-hard。据我们所知，即使在非翻译不变的情况下，CSP在网格上也没有任何差距结果。作为我们结果的副产品，我们还表明，优化问题的决策版本询问最佳分配的成本是否奇怪，甚至对于$ p^{nexp} $也是完整的。
We study the complexity of classical constraint satisfaction problems on a 2D grid. Specifically, we consider the complexity of function versions of such problems, with the additional restriction that the constraints are translationally invariant, namely, the variables are located at the vertices of a 2D grid and the constraint between every pair of adjacent variables is the same in each dimension. The only input to the problem is thus the size of the grid. This problem is equivalent to one of the most interesting problems in classical physics, namely, computing the lowest energy of a classical system of particles on the grid. We provide a tight characterization of the complexity of this problem, and show that it is complete for the class $FP^{NEXP}$. Gottesman and Irani (FOCS 2009) also studied classical translationally-invariant constraint satisfaction problems; they show that the problem of deciding whether the cost of the optimal solution is below a given threshold is NEXP-complete. Our result is thus a strengthening of their result from the decision version to the function version of the problem. Our result can also be viewed as a generalization to the translationally invariant setting, of Krentel's famous result from 1988, showing that the function version of SAT is complete for the class $FP^{NP}$. An essential ingredient in the proof is a study of the complexity of a gapped variant of the problem. We show that it is NEXP-hard to approximate the cost of the optimal assignment to within an additive error of $Ω(N^{1/4})$, for an $N \times N$ grid. To the best of our knowledge, no gapped result is known for CSPs on the grid, even in the non-translationally invariant case. As a byproduct of our results, we also show that a decision version of the optimization problem which asks whether the cost of the optimal assignment is odd or even is also complete for $P^{NEXP}$.
