论文标题
随机max-csps从旋转眼镜继承算法硬度
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
论文作者
论文摘要
我们研究不满意的制度中的随机约束满意度问题（CSP）。我们使用统计物理学的Guerra-Toninelli插值将对HyperCube上相关的自旋玻璃的近最佳解决方案的结构与相关的自旋玻璃联系起来。 CSP谓词的噪声稳定性多项式是相关自旋玻璃的混合物多项式的常数。我们证明了两个主要后果： 1）我们将可以在随机的Max-CSP中满足的约束的最大分数与相应自旋玻璃的基态能量密度相关联。由于可以使用巴黎公式计算后一个值，因此我们为一些流行的CSP提供数值。 2）我们证明，当且仅当相应的自旋玻璃相同时，Max-CSP具有重叠间隙属性的广义版本。我们从Huang等人传递结果。 [Arxiv：2110.07847，2021]在大型的Max-CSP上阻碍重叠浓度的算法。这立即包括本地经典和局部量子算法。
We study random constraint satisfaction problems (CSPs) in the unsatisfiable regime. We relate the structure of near-optimal solutions for any Max-CSP to that for an associated spin glass on the hypercube, using the Guerra-Toninelli interpolation from statistical physics. The noise stability polynomial of the CSP's predicate is, up to a constant, the mixture polynomial of the associated spin glass. We prove two main consequences: 1) We relate the maximum fraction of constraints that can be satisfied in a random Max-CSP to the ground state energy density of the corresponding spin glass. Since the latter value can be computed with the Parisi formula, we provide numerical values for some popular CSPs. 2) We prove that a Max-CSP possesses generalized versions of the overlap gap property if and only if the same holds for the corresponding spin glass. We transfer results from Huang et al. [arXiv:2110.07847, 2021] to obstruct algorithms with overlap concentration on a large class of Max-CSPs. This immediately includes local classical and local quantum algorithms.
