research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleOn the satisfiability threshold of formulas with three literals per clause
Bibtex cite IDRACTI-RU1-2009-32
Journal Theoretical Computer Science (TCS)
Year published 2009
In this paper we present a new upper bound for randomly chosen 3-CNF formulas. In particular we show that any random formula over n variables, with a clauses-to-variables ratio of at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was 4.506. The first such bound, independently discovered by many groups of researchers since 1983, was 5.19. Several decreasing values between 5.19 and 4.506 were published in the years between.We believe that the probabilistic techniques we use for the proof are of independent interest.
Diaz, Josep
Kirousis, Lefteris
Mitsche, Dieter
Perez, X
satisfiability.pdf (main file)
Publication ID675