The probabilistic analysis of a greedy satisfiability algorithm

Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Consider the following simple, greedy Davis-Putnam algorithm applied to a random 3-CNF formula of constant density c: Arbitrarily set to TRUE a literal that appears in as many clauses as possible, irrespective of their size (and irrespective of the number of occurrences of the negation of the literal). Reduce the formula. If any unit clauses appear, then satisfy their literals arbitrarily, reducing the formula accordingly, until no unit clause remains. Repeat. We prove that for c< 3.42 a slight modification of this algorithm computes a satisfying truth assignment with probability asymptotically bounded away from zero. Previously, algorithms of increasing sophistication were shown to succeed for c< 3.26. Preliminary experiments we performed suggest that c≈3.6 is feasible running algorithms like the above, which take into account not only the number of occurrences of a literal but also the number of occurrences of its negation, irrespectively of clause-size information.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
EditorsRolf Möhring, Rajeev Raman
PublisherSpringer Verlag
Number of pages13
ISBN (Electronic)3540441808, 9783540441809
StatePublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other10th Annual European Symposium on Algorithms, ESA 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The probabilistic analysis of a greedy satisfiability algorithm'. Together they form a unique fingerprint.

Cite this