TY - GEN

T1 - On the accuracy and running time of GSAT

AU - East, Deborah

AU - Truszczyński, Miroslaw

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84957633928&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957633928&partnerID=8YFLogxK

U2 - 10.1007/3-540-48159-1_4

DO - 10.1007/3-540-48159-1_4

M3 - Conference contribution

AN - SCOPUS:84957633928

SN - 354066548X

SN - 9783540665489

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 61

BT - Progress in Artificial Intelligence - 9th Portuguese Conference on Artificial Intelligence, EPIA 1999, Proceedings

A2 - Barahona, Pedro

A2 - Alferes, José J.

Y2 - 21 September 1999 through 24 September 1999

ER -