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 -