A Randomized Algorithm for 3-SAT

Details A Randomized Algorithm for 3-SAT A Randomized Algorithm for 3-SAT

2009-06-10

arxiv.org/abs/0906.1849v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this work we propose and analyze a simple randomized 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 in{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 Journal of Theoretical Computer Science 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 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 per variable that appear as unique true literal in one or more critical clauses in phi is between 1 and 1.9317, combined algorithm performs better than the PPZ algorithm.

Affiliated with

Also associated with

No associations

Rating

A Randomized Algorithm for 3-SAT 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 A Randomized Algorithm for 3-SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Randomized Algorithm for 3-SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206348