https://hal.inria.fr/hal-00959018Puyhaubert, VincentVincentPuyhaubertALGORITHMS - Algorithms - Inria Paris-Rocquencourt - Inria - Institut National de Recherche en Informatique et en AutomatiqueGenerating functions and the satisfiability thresholdHAL CCSD2004exponential generating functionssaddle-point boundsFirst moment method[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Inria Sophia Antipolis-Méditerranée / I3s, Service Ist2014-03-13 17:06:292022-02-04 03:08:392014-03-13 21:14:01enJournal articleshttps://hal.inria.fr/hal-00959018/document10.46298/dmtcs.325application/pdf1The 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.