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 $\Omega(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}$.
翻译:我们研究的是2D网格上传统约束性满意度问题的复杂性。 具体地说, 我们考虑的是这类问题功能版本的复杂性, 其复杂性是翻译性的, 额外的限制是: 变量位于2D网格的顶端, 每对相邻变量之间的限制在每个维度都是相同的。 因此, 问题的唯一投入是网格的大小。 这个问题相当于经典物理学中最有趣的问题之一, 即 计算网格上传统粒子系统的最低能量。 我们对此问题的复杂性作了严格的描述, 并表明对于 $FP\NEXP 来说, 已经完全完成了。 Gotesman 和 Irani (FOCS 2009) 还研究了典型的翻译性差异性约束性满意度问题。 它们表明, 最佳解决方案的成本是否低于给定限值。 因此, 我们决定版本到问题功能版本的“ 美元” 。 我们的结果也可以被看成是全面化的变值, Krentel 的变值, 在1988年版本中, 最精度的变数的变数是 。