10.4230/LIPICS.FSTTCS.2008.1750
Diaz, Josep
Josep
Diaz
Kirousis, Lefteris
Lefteris
Kirousis
Mitsche, Dieter
Dieter
Mitsche
Perez-Gimenez, Xavier
Xavier
Perez-Gimenez
A new upper bound for 3-SAT
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Satisfiability
3-SAT
random
threshold
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17507
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
6
163
174
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
481316 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 163-174