On the accuracy and running time of GSAT

Deborah East, Miroslaw Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


Randomized algorithms for deciding satisfiability were shown to be effective in solving problems with thousands of variables. However, these algorithms are not complete. That is, they provide no guarantee that a satisfying assignment, if one exists, will be found. Thus, when studying randomized algorithms, there are two important characteristics that need to be considered: the running time and, even more importantly, the accuracy - a measure of likelihood that a satisfying assignment will be found, provided one exists. In fact, we argue that without a reference to the accuracy, the notion of the running time for randomized algorithms is not well-defined. In this paper, we introduce a formal notion of accuracy. We use it to define a concept of the running time. We use both notions to study the random walk strategy GSAT algorithm. We investigate the dependence of accuracy on properties of input formulas such as clause-to-variable ratio and the number of satisfying assignments. We demonstrate that the running time of GSAT grows exponentially in the number of variables of the input formula for randomly generated 3-CNF formulas and for the formulas encoding 3- and 4-colorability of graphs.

Original languageEnglish
Title of host publicationProgress in Artificial Intelligence - 9th Portuguese Conference on Artificial Intelligence, EPIA 1999, Proceedings
EditorsPedro Barahona, José J. Alferes
Number of pages13
StatePublished - 1999
Event9th Portuguese Conference on Progress in Artificial Intelligence, EPIA 1999 - Evora, Portugal
Duration: Sep 21 1999Sep 24 1999

Publication series

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


Conference9th Portuguese Conference on Progress in Artificial Intelligence, EPIA 1999

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the accuracy and running time of GSAT'. Together they form a unique fingerprint.

Cite this