Computer Science – Artificial Intelligence
Scientific paper
2000-02-04
Computer Science
Artificial Intelligence
Proceedings of the 9th Portuguese Conference on Artificial Intelligence (EPIA'99), Lecture Notes in Artificial Intelligence, v
Scientific paper
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.
East Deborah
Truszczynski Miroslaw
No associations
LandOfFree
On the accuracy and running time of GSAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the accuracy and running time of GSAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the accuracy and running time of GSAT will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-232914