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 条
  • [1] Recognizing more unsatisfiable random 3-SAT instances efficiently
    Friedman, J
    Goerdt, A
    AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING, 2001, 2076 : 310 - 321
  • [2] Implementing 3-SAT Gadgets for Quantum Annealers with Random Instances
    Rodriguez-Farres, Pol
    Ballester, Rocco
    Ansotegui, Carlos
    Levy, Jordi
    Cerquides, Jesus
    COMPUTATIONAL SCIENCE, ICCS 2024, PT VI, 2024, 14937 : 277 - 291
  • [3] Generating "Random" 3-SAT instances with specific solution space structure
    Pari, PR
    Lin, J
    Yuan, L
    Qu, G
    PROCEEDING OF THE NINETEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE SIXTEENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2004, : 960 - 961
  • [4] HyperSAT a new generator for 3-SAT instances
    Segura-Salazar, J
    Torres-Jiménez, J
    ICCIMA 2001: FOURTH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND MULTIMEDIA APPLICATIONS, PROCEEDINGS, 2001, : 323 - 327
  • [5] Computational complexity of some restricted instances of 3-SAT
    Berman, Piotr
    Karpinski, Marek
    Scott, Alexander D.
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (05) : 649 - 653
  • [6] The maximum length of prime implicates for instances of 3-SAT
    Dunne, PE
    BenchCapon, TJM
    ARTIFICIAL INTELLIGENCE, 1997, 92 (1-2) : 317 - 329
  • [7] Random 3-SAT: The Plot Thickens
    Cristian Coarfa
    Demetrios D. Demopoulos
    Alfonso San Miguel Aguirre
    Devika Subramanian
    Moshe Y. Vardi
    Constraints, 2003, 8 : 243 - 261
  • [8] Random 3-SAT: The plot thickens
    Coarfa, C
    Demopoulos, DD
    Aguirre, AS
    Subramanian, D
    Vardi, MY
    CONSTRAINTS, 2003, 8 (03) : 243 - 261
  • [9] Improving WalkSAT for Random 3-SAT Problems
    Fu, Huimin
    Xu, Yang
    Chen, Shuwei
    Liu, Jun
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2020, 26 (02) : 220 - 243
  • [10] Optimal myopic algorithms for random 3-SAT
    Achlioptas, D
    Sorkin, GB
    41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, : 590 - 600
12345