A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

✍ Scribed by O Dubois; Y Boufkhad

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 280 KB
• Volume: 24
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0867

✦ Synopsis

Experiments on solving r-SAT random formulae have provided evidence of a satisfiability threshold phenomenon with respect to the ratio of the number of clauses to the number of variables of formulae. Presently, only the threshold of 2-SAT formulae has been proved to exist and has been computed to be equal to 1. For 3-SAT formulae and more generally for r-SAT formulae, lower and upper bounds of the threshold have been established. The best established bounds concern 3-SAT. For an observed threshold of about 4.25, the best lower bound is 3.003 and the best upper bound 4.76. In this paper we establish a general upper bound of the threshold for r-SAT formulae giving a value for 3-SAT of 4.64, significantly improving the previous best upper bound. For this we have defined a more restrictive structure than a satisfying truth assignment for characterizing the satisfiability of a SAT formula which we have called negatively prime solution Ž . NPS . By merely applying the first moment method to negatively prime solutions of a random r-SAT formula we obtain our bound.