Negative slope coefficient and the difficulty of random 3-SAT instances

被引：0

作者：

Tomassini, Marco ^{[1
]}

Vanneschi, Leonardo ^{[2
]}

机构：

[1] Univ Lausanne, Dept Informat Syst, Lausanne, Switzerland

[2] Univ Milano Bicocca, Dept Informat, Sys Commun, I-20122 Milan, Italy

来源：

APPLICATIONS OF EVOLUTIONARY COMPUTING, PROCEEDINGS | 2008年 / 4974卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper we present an empirical study of the Negative Slope Coefficient (NSC) hardness statistic to characterize the difficulty of 3-SAT fitness landscapes for randomly generated problem instances. NSC correctly classifies problem instances with a low ratio of clauses to variables as easy, while instances with a ratio close to the critical point are classified as hard, as expected. Together with previous results on many different problems and fitness landscapes, the present results confirm that NSC is a useful and reliable indicator of problem difficulty.

引用

页码：643 / +

页数：2

共 50 条

[21] Revisiting the cavity-method threshold for random 3-SAT
Lundow, P. H.
Markstrom, K.
[J]. PHYSICAL REVIEW E, 2019, 99 (02)
[22] On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
Maneva, Elitza
Sinclair, Alistair
[J]. THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) : 359 - 369
[23] Notions of average-case complexity for random 3-SAT
Atserias, A
[J]. COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2004, 3210 : 1 - 5
[24] Dynamic variable filtering for hard random 3-SAT problems
Anbulagan
Thornton, J
Sattar, A
[J]. AI 2003: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2003, 2903 : 100 - 111
[25] Hidden structure in unsatisfiable random 3-SAT: an empirical study
Lynce, I
Marques-Silva, J
[J]. ICTAI 2004: 16TH IEEE INTERNATIONALCONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2004, : 246 - 251
[26] On the limit of branching rules for hard random unsatisfiable 3-SAT
Li, CM
Gérard, S
[J]. DISCRETE APPLIED MATHEMATICS, 2003, 130 (02) : 277 - 290
[27] On the limit of branching rules for hard random unsatisfiable 3-SAT
Li, Chu-Min
Gérard, Sylvain
[J]. Discrete Appl Math, 2 (277-290):
[28] On the Empirical Time Complexity of Random 3-SAT at the Phase Transition
Mu, Zongxu
Hoos, Holger H.
[J]. PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 367 - 373
[29] On the limit of branching rules for hard random unsatisfiable 3-SAT
Li, CM
Gérard, S
[J]. ECAI 2000: 14TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2000, 54 : 98 - 102
[30] Lower bounds for random 3-SAT via differential equations
Achlioptas, D
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 265 (1-2) : 159 - 185

← 1 2 3 4 5 →