Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem

被引：29

作者：

Ardelius, John ^{[1
]}

Zdeborovae, Lenka ^{[2
]}

机构：

[1] Swedish Inst Comp Sci, SE-16424 Kista, Sweden

[2] Univ Paris Sud, LPTMS, CNRS, UMR8626, F-91405 Orsay, France

来源：

PHYSICAL REVIEW E | 2008年 / 78卷 / 04期

关键词：

D O I：

10.1103/PhysRevE.78.040101

中图分类号：

O35 [流体力学]; O53 [等离子体物理学];

学科分类号：

070204 ; 080103 ; 080704 ;

摘要：

We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions, which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.

引用

页数：4

共 36 条

[1]

Achlioptas D., 2006, STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, P130, DOI 10.1145/1132516.1132537

[2]

[Anonymous], 1987, WORLD SCI LECT NOTES

[3] Behavior of heuristics on large and hard satisfiability problems [J].

Ardelius, John ;

Aurell, Erik .

PHYSICAL REVIEW E, 2006, 74 (03)

[4]

Bayardo RJ, 2000, SEVENTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-2001) / TWELFTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE (IAAI-2000), P157

[5] A variational description of the ground state structure in random satisfiability problems [J].

Biroli, G ;

Monasson, R ;

Weigt, M .

EUROPEAN PHYSICAL JOURNAL B, 2000, 14 (03) :551-568

[6] Survey-propagation decimation through distributed local computations -: art. no. P11016 [J].

Chavas, J ;

Furtlehner, C ;

Mézard, M ;

Zecchina, R .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :300-325

[7]

Cheeseman P C., 1991, INT JOINT C ARTIFICI, V91, P331

[8] Efficient program synthesis using constraint satisfaction in inductive logic programming [J].

Ahlgren, John ;

Yuen, Shiu Yin .

2013, Microtome Publishing (14) :3649-3681

[9] Entropy landscape and non-Gibbs solutions in constraint satisfaction problems [J].

Dall'Asta, L. ;

Ramezanpour, A. ;

Zecchina, R. .

PHYSICAL REVIEW E, 2008, 77 (03)

[10] Sharp thresholds of graph properties, and the k-sat problem [J].

Friedgut, E .

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1999, 12 (04) :1017-1054

← 1 2 3 4 →