Geodesic
Generating functions and the satisfiability threshold
Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2004_6_2_a14,
     author = {Puyhaubert, Vincent},
     title = {Generating functions and the satisfiability threshold},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {6},
     number = {2},
     year = {2003-2004},
     doi = {10.46298/dmtcs.325},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.325/}
}
TY  - JOUR
AU  - Puyhaubert, Vincent
TI  - Generating functions and the satisfiability threshold
JO  - Discrete mathematics & theoretical computer science
PY  - 2003-2004
VL  - 6
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.325/
DO  - 10.46298/dmtcs.325
LA  - en
ID  - DMTCS_2004_6_2_a14
ER  - 
%0 Journal Article
%A Puyhaubert, Vincent
%T Generating functions and the satisfiability threshold
%J Discrete mathematics & theoretical computer science
%D 2003-2004
%V 6
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.325/
%R 10.46298/dmtcs.325
%G en
%F DMTCS_2004_6_2_a14
Puyhaubert, Vincent. Generating functions and the satisfiability threshold. Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 2. doi : 10.46298/dmtcs.325. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.325/

Cité par Sources :