Behavior of heuristics on large and hard satisfiability problems

被引：34

作者：

Ardelius, John ^{[1
]}

Aurell, Erik

机构：

[1] AlbaNova Univ Ctr, Royal Inst Technol, KTH, SE-10691 Stockholm, Sweden

[2] SICS Swedish Inst Comp Sci AB, Kista, Sweden

来源：

PHYSICAL REVIEW E | 2006年 / 74卷 / 03期

关键词：

D O I：

10.1103/PhysRevE.74.037702

中图分类号：

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

学科分类号：

070204 [等离子体物理]; 080103 [流体力学]; 080704 [流体机械及工程];

摘要：

We study the behavior of a heuristic for solving random satisfiability problems by stochastic local search near the satisfiability threshold. The heuristic for average satisfiability (ASAT), is similar to the Focused Metropolis Search heuristic, and shares the property of being focused, i.e., only variables in unsatisfied clauses are updated in each step. It is significantly simpler than the benchmark WALKSAT heuristic. We show that ASAT solves instances as large as N=10(6) in linear time, on average, up to a ratio of 4.21 clauses per variable in random three-satisfiability. For K higher than 3, ASAT appears to solve instances of K-satisfiability up to the Montanari-Ricci-Tersenghi-Parisi full replica symmetry breaking (FSRB) threshold denoted alpha(s)(K) in linear time.

引用

页数：4

共 22 条

[1]

Rigorous location of phase transitions in hard optimization problems [J].

Achlioptas, D ;

Naor, A ;

Peres, Y .

NATURE, 2005, 435 (7043) :759-764

[2]

AURELL E, 2004, 18 ANN C NEUR INF PR

[3]

Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms [J].

Barthel, W ;

Hartmann, AK ;

Weigt, M .

PHYSICAL REVIEW E, 2003, 67 (06) :15

[4]

Optimizing at the ergodic edge [J].

Boettcher, Stefan ;

Frank, Martin .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2006, 367 :220-230

[5]

Trajectories in phase diagrams, growth processes, and computational complexity: How search algorithms solve the 3-satisfiability problem [J].

Cocco, S ;

Monasson, R .

PHYSICAL REVIEW LETTERS, 2001, 86 (08) :1654-1657

[6]

DYNAMICS OF SPIN SYSTEMS WITH RANDOMLY ASYMMETRIC BONDS - LANGEVIN DYNAMICS AND A SPHERICAL MODEL [J].

CRISANTI, A ;

SOMPOLINSKY, H .

PHYSICAL REVIEW A, 1987, 36 (10) :4922-4939

[7]

Glassy behaviour in disordered systems with nonrelaxational dynamics [J].

Cugliandolo, LF ;

Kurchan, J ;

LeDoussal, P ;

Peliti, L .

PHYSICAL REVIEW LETTERS, 1997, 78 (02) :350-353

[8]

DEROULERS C, 1996, ADV NEURAL INFORM PR, V17, P521

[9]

DUBOIS O, 2001, THEOR COMPUT SCI, V265

[10]

HBARTMANN AK, 2001, PHASE TRANSITIONS CO

← 1 2 3 →