A theoretical analysis of the k-satisfiability search space

Andrew M. Sutton, Adele E. Howe, L. Darrell Whitley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

Local search algorithms perform surprisingly well on the k-satisfiability (k-SAT) problem. However, few theoretical analyses of the k-SAT search space exist. In this paper we study the search space of the k-SAT problem and show that it can be analyzed by a decomposition. In particular, we prove that the objective function can be represented as a superposition of exactly k elementary landscapes. We show that this decomposition allows us to immediately compute the expectation of the objective function evaluated across neighboring points. We use this result to prove previously unknown bounds for local maxima and plateau width in the 3-SAT search space. We compute these bounds numerically for a number of instances and show that they are non-trivial across a large set of benchmarks.

Original languageEnglish (US)
Title of host publicationEngineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics - Second International Workshop, SLS 2009, Proceedings
Pages46-60
Number of pages15
DOIs
StatePublished - Nov 4 2009
Event2nd International Workshop on Engineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics, SLS 2009 - Brussels, Belgium
Duration: Sep 3 2009Sep 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5752 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Engineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics, SLS 2009
CountryBelgium
CityBrussels
Period9/3/099/4/09

Fingerprint Dive into the research topics of 'A theoretical analysis of the k-satisfiability search space'. Together they form a unique fingerprint.

Cite this