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. © 2008 Springer-Verlag Berlin Heidelberg.

Tomassini, M., Vanneschi, L. (2008). Negative Slope coefficient and the difficulty of random 3-SAT instances. In Applications of Evolutionary Computing. EvoWorkshops 2008 (pp.643-648). Berlin : Springer [10.1007/978-3-540-78761-7_70].

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

VANNESCHI, LEONARDO
2008

Abstract

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. © 2008 Springer-Verlag Berlin Heidelberg.
paper
negative, slope, coefficient, difficulty, random, sat, instances
English
International Workshop on Theoretical Aspects in Artificial Evolution
2008
Applications of Evolutionary Computing. EvoWorkshops 2008
9783540787600
2008
4974
643
648
none
Tomassini, M., Vanneschi, L. (2008). Negative Slope coefficient and the difficulty of random 3-SAT instances. In Applications of Evolutionary Computing. EvoWorkshops 2008 (pp.643-648). Berlin : Springer [10.1007/978-3-540-78761-7_70].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/13585
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
Social impact