Relaxation and metastability in a local search procedure for the random satisfiability problem

Guilhem Semerjian; Rémi Monasson

Relaxation and metastability in a local search procedure for the random satisfiability problem

Guilhem Semerjian
, Rémi Monasson

Center for Atomic-scale Materials Physics (CAMP)
Université de Strasbourg

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

Relaxation and..... A study was conducted on the dynamics of a simple search procedure for the satisfaction of Boolean constraints, the RandomWalkSAT algorithm. It was shown using complementary techniques that, for randmly drawn input instances, RandomWalkSAT may have two qualitatively distinct behaviors. Instances with small ratios α of clauses pervariable were almost surely solved in a time growing linearly with their size.

langue originale	Anglais
Numéro d'article	066103
Pages (de - à)	066103/1-066103/18
journal	Physical Review E
Volume	67
Numéro de publication	6 2
état	Publié - 1 juin 2003
Modification externe	Oui

Contient cette citation

@article{41a90b6d77fd4a7c8496e75ce5acd1c8,

title = "Relaxation and metastability in a local search procedure for the random satisfiability problem",

abstract = "Relaxation and..... A study was conducted on the dynamics of a simple search procedure for the satisfaction of Boolean constraints, the RandomWalkSAT algorithm. It was shown using complementary techniques that, for randmly drawn input instances, RandomWalkSAT may have two qualitatively distinct behaviors. Instances with small ratios α of clauses pervariable were almost surely solved in a time growing linearly with their size.",

author = "Guilhem Semerjian and R{\'e}mi Monasson",

year = "2003",

month = jun,

day = "1",

language = "English",

volume = "67",

pages = "066103/1--066103/18",

journal = "Physical Review E",

issn = "2470-0045",

number = "6 2",

}

TY - JOUR

T1 - Relaxation and metastability in a local search procedure for the random satisfiability problem

AU - Semerjian, Guilhem

AU - Monasson, Rémi

PY - 2003/6/1

Y1 - 2003/6/1

N2 - Relaxation and..... A study was conducted on the dynamics of a simple search procedure for the satisfaction of Boolean constraints, the RandomWalkSAT algorithm. It was shown using complementary techniques that, for randmly drawn input instances, RandomWalkSAT may have two qualitatively distinct behaviors. Instances with small ratios α of clauses pervariable were almost surely solved in a time growing linearly with their size.

AB - Relaxation and..... A study was conducted on the dynamics of a simple search procedure for the satisfaction of Boolean constraints, the RandomWalkSAT algorithm. It was shown using complementary techniques that, for randmly drawn input instances, RandomWalkSAT may have two qualitatively distinct behaviors. Instances with small ratios α of clauses pervariable were almost surely solved in a time growing linearly with their size.

M3 - Article

AN - SCOPUS:42749101961

SN - 2470-0045

VL - 67

SP - 066103/1-066103/18

JO - Physical Review E

JF - Physical Review E

IS - 6 2

M1 - 066103

ER -

Relaxation and metastability in a local search procedure for the random satisfiability problem

Résumé

Empreinte digitale

Contient cette citation