A new upper bound for 3-SAT

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

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

Abstract

We show that a randomly chosen 3-CNF formula over n variables with clauses-to-variables ratio at least 4.4898 is 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. The probabilistic techniques we use for the proof are, we believe, of independent interest.

Original languageEnglish (US)
Title of host publicationFSTTCS 2008 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Pages163-174
Number of pages12
StatePublished - 2008
Event28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008 - Bangalore, India
Duration: Dec 9 2008Dec 11 2008

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume2
ISSN (Print)1868-8969

Conference

Conference28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008
Country/TerritoryIndia
CityBangalore
Period12/9/0812/11/08

Keywords

  • 3-SAT
  • Random
  • Satisfiability
  • Threshold

ASJC Scopus subject areas

  • Software

Cite this