Paper Info
Title
A Randomized Algorithm For 3-Sat
Abstract
In this work we propose and analyze a simple randomized algorithm for 3-SAT (i.e. an algorithm to find a satisfiable assignment for a Boolean formula in conjunctive normal form (CNF) having at most 3 literals in every clause). Given a k-CNF formula phi on n variables, and alpha is an element of {0, 1}(n) that satisfies phi, a clause of phi is critical if exactly one literal of that clause is satisfied under assignment alpha. Paturi et al. (Chicago J. Theor. Comput. Sci. 115, 1999) proposed a simple randomized algorithm (PPZ) for k-SAT for which success probability increases with the number of critical clauses (with respect to a fixed satisfiable solution of the input formula). Here, we first describe another simple randomized algorithm DEL which performs better if the number of critical clauses in input formula are less (with respect to a fixed satisfiable solution of the input formula). Subsequently, we combine these two simple algorithms such that the success probability of the combined algorithm is maximum of the success probabilities of PPZ and DEL on every input instance. We show that when the average number of clauses for a variable that appear as unique true literals in one or more critical clauses in phi is between 1 and 2/(3 center dot log (3/2)), combined algorithm performs better than the PPZ algorithm.
Year
DOI
Venue
2009
10.1007/s11786-010-0036-3
MATHEMATICS IN COMPUTER SCIENCE
Keywords
DocType
Volume
Boolean satisfiability, Randomized algorithm, Exponential time algorithm, Analysis of algorithms
Journal
3
Issue
ISSN
Citations 
4
1661-8270
0
PageRank 
References 
Authors
0.34
7
2
Name
Order
Citations
PageRank
Subhas Kumar Ghosh1315.65
Janardan Misra216514.33