2026-07-21T19:38:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1750 2024-03-06T10:33:04Z ddc:004 open_access

A new upper bound for 3-SAT Diaz, Josep Kirousis, Lefteris Mitsche, Dieter Perez-Gimenez, Xavier Satisfiability 3-SAT random threshold 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Josep Diaz and Lefteris Kirousis and Dieter Mitsche and Xavier Perez-Gimenez 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1750 urn:nbn:de:0030-drops-17507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1750 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode