Reconstruction and Clustering in Random Constraint Satisfaction Problems
Reconstruction and Clustering in Random Constraint Satisfaction Problems
复制标题
随机约束满足问题中的重构和聚类
DOI：
--
复制
发表时间：
2009
影响因子：
0.8
通讯作者：
P. Tetali
中科院分区：
文献类型：
--
作者：
A. Montanari;R. Restrepo;P. Tetali
当每个变量的约束数量位于某个区间时，约束满足问题 (CSP) 的随机实例对于所有已知算法来说似乎都很困难。为了有助于对可满足体系中 CSP 解空间结构的一般理解，我们在一大群随机 CSP 上制定了一组技术条件，并证明了这种集成的密度的三个最有趣阈值的界限：即可满足性阈值、解空间聚类阈值以及 CSP 上适当重构问题的阈值。随着每个子句中自由度数量的不同，界限变得渐近紧密。这些系列足够通用，包括常见的研究问题，例如非全等 SAT 的随机实例、k-XOR 公式、超图 2-着色和图 k-着色。一个重要的新成分是涉及子句傅立叶展开的条件，它表征了...的类别
Random instances of constraint satisfaction problems (CSPs) appear to be hard for all known algorithms when the number of constraints per variable lies in a certain interval. Contributing to the general understanding of the structure of the solution space of a CSP in the satisfiable regime, we formulate a set of technical conditions on a large family of random CSPs and prove bounds on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and the threshold for an appropriate reconstruction problem on the CSPs. The bounds become asymptoticlally tight as the number of degrees of freedom in each clause diverges. The families are general enough to include commonly studied problems such as random instances of Not-All-Equal SAT, k-XOR formulae, hypergraph 2-coloring, and graph k-coloring. An important new ingredient is a condition involving the Fourier expansion of clauses, which characterizes the class of ...