论文标题
随机常规nae-sat i的一步复制对称破坏
One-step replica symmetry breaking of random regular NAE-SAT I
论文作者
论文摘要
在一系列稀疏的随机约束满意度问题（CSP）中，来自统计物理学的深度启发式学预测，在满足性阈值之前存在凝结相变，该阈值受一步复制对称性破坏（1RSB）的控制。实际上，在随机的k-nae-sat中，这是这样一个随机的CSP之一，已验证\ cite {ssz22}，其自由能是明确定义的，并且显式值遵循1RSB的预测。但是，对于任何稀疏随机CSP的模型，尚不清楚该解空间是否确实根据1RSB预测在O（1）簇上凝结。在本文中，我们为随机的常规K-NAE-SAT模型给出了这个问题的肯定答案。也就是说，我们证明，由于概率远离零，大多数解决方案都位于有界数的溶液簇内，其大小与自由能的规模相媲美。此外，我们确定两个独立绘制的溶液之间的重叠精确地集中在两个值下。我们的证明是基于对自旋系统的详细力矩分析，该分析具有编码溶液簇结构的无限旋转空间。我们认为，我们的方法适用于1RSB通用类中的各种随机CSP。
In a broad class of sparse random constraint satisfaction problems(CSP), deep heuristics from statistical physics predict that there is a condensation phase transition before the satisfiability threshold, governed by one-step replica symmetry breaking(1RSB). In fact, in random regular k-NAE-SAT, which is one of such random CSPs, it was verified \cite{ssz22} that its free energy is well-defined and the explicit value follows the 1RSB prediction. However, for any model of sparse random CSP, it has been unknown whether the solution space indeed condenses on O(1) clusters according to the 1RSB prediction. In this paper, we give an affirmative answer to this question for the random regular k-NAE-SAT model. Namely, we prove that with probability bounded away from zero, most of the solutions lie inside a bounded number of solution clusters whose sizes are comparable to the scale of the free energy. Furthermore, we establish that the overlap between two independently drawn solutions concentrates precisely at two values. Our proof is based on a detailed moment analysis of a spin system, which has an infinite spin space that encodes the structure of solution clusters. We believe that our method is applicable to a broad range of random CSPs in the 1RSB universality class.
