TY - JOUR
T1 - On the satisfiability threshold of formulas with three literals per clause
AU - Díaz, J.
AU - Kirousis, L.
AU - Mitsche, D.
AU - Pérez-Giménez, X.
PY - 2009/8/20
Y1 - 2009/8/20
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=67649771831&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67649771831&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2009.02.020
DO - 10.1016/j.tcs.2009.02.020
M3 - Article
AN - SCOPUS:67649771831
SN - 0304-3975
VL - 410
SP - 2920
EP - 2934
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 30-32
ER -