The probabilistic analysis of a greedy satisfiability algorithm
- 8 November 2005
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 28 (4) , 444-480
Abstract
On input a random 3‐CNF formula of clauses‐to‐variables ratior3applies repeatedly the following simple heuristic: Set to True a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1‐clauses when they appear get priority). We prove that forr3< 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed forr3< 3.26. We improve up tor3< 3.52 by further exploiting the degree of the negation of the evaluated to True literal. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006Keywords
This publication has 49 references indexed in Scilit:
- On the critical exponents of randomk-SATRandom Structures & Algorithms, 2002
- Upper bounds on the satisfiability thresholdTheoretical Computer Science, 2001
- Results related to threshold phenomena research in satisfiability: lower boundsTheoretical Computer Science, 2001
- Lower bounds for random 3-SAT via differential equationsTheoretical Computer Science, 2001
- Random 2-SAT and unsatisfiabilityInformation Processing Letters, 1999
- 2+p-SAT: Relation of typical-case complexity to the nature of the phase transitionRandom Structures & Algorithms, 1999
- The degree sequence of a random graph. I. The modelsRandom Structures & Algorithms, 1997
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT FormulaeJournal of Algorithms, 1997
- Analysis of Two Simple Heuristics on a Random Instance ofk-satJournal of Algorithms, 1996
- Probabilistic analysis of the pure literal heuristic for the satisfiability problemAnnals of Operations Research, 1984