Generating functions and the satisfiability threshold

Vincent Puyhaubert 1
1 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
Abstract : The 3-SAT problem consists in determining if a boolean formula with 3 literals per clause is satisfiable. When the ratio between the number of clauses and the number of variables increases, a threshold phenomenon is observed: the probability of satisfiability appears to decrease sharply from 1 to 0 in the neighbourghood of a threshold value, conjectured to be close to 4.25. Although the threshold has been proved to exist for the 2-SAT formulæ and for closely related problems like 3-XORSAT, there is still no proof for the 3-sat problem. Recent works have provided so far upper and lower bounds for the threshold's potential location. We present here a unified approach to upper bounds that is based on urn models, generating functions, and saddle-point bounds. In this way, we re-derive some of the most significant upper bounds known in a simple and uniform manner.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.425-436
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00959018
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 17:06:29
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:17:54

Fichier

dm060216.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00959018, version 1

Collections

Citation

Vincent Puyhaubert. Generating functions and the satisfiability threshold. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.425-436. 〈hal-00959018〉

Partager

Métriques

Consultations de la notice

167

Téléchargements de fichiers

169