On the satisfiability threshold of formulas with three literals per clause

J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Giménez

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2920-2934
Number of pages15
JournalTheoretical Computer Science
Volume410
Issue number30-32
DOIs
StatePublished - Aug 20 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On the satisfiability threshold of formulas with three literals per clause'. Together they form a unique fingerprint.

Cite this