Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability

Creignou, Nadia; Daudé, Hervé

doi:10.1051/ita:2003014

Smooth and sharp thresholds for random

k

-XOR-CNF satisfiability

Creignou, Nadia ; Daudé, Hervé

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 127-147.

Résumé

The aim of this paper is to study the threshold behavior for the satisfiability property of a random $k$ -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with $k$ variables per equation. For $k \geq 3$ we show the existence of a sharp threshold for the satisfiability of a random $k$ -XOR-CNF formula, whereas there are smooth thresholds for $k = 1$ and $k = 2$ .

MR Zbl

DOI : 10.1051/ita:2003014

Classification : 05C80, 68R05, 60C05
Mots clés : threshold phenomenon, satisfiability, phase transition, random boolean linear systems

@article{ITA_2003__37_2_127_0,
     author = {Creignou, Nadia and Daud\'e, Herv\'e},
     title = {Smooth and sharp thresholds for random ${k}${-XOR-CNF} satisfiability},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {127--147},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {2},
     year = {2003},
     doi = {10.1051/ita:2003014},
     mrnumber = {2015688},
     zbl = {1112.68390},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2003014/}
}

TY  - JOUR
AU  - Creignou, Nadia
AU  - Daudé, Hervé
TI  - Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2003
SP  - 127
EP  - 147
VL  - 37
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003014/
DO  - 10.1051/ita:2003014
LA  - en
ID  - ITA_2003__37_2_127_0
ER  -

%0 Journal Article
%A Creignou, Nadia
%A Daudé, Hervé
%T Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2003
%P 127-147
%V 37
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2003014/
%R 10.1051/ita:2003014
%G en
%F ITA_2003__37_2_127_0

Creignou, Nadia; Daudé, Hervé. Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 127-147. doi : 10.1051/ita:2003014. http://www.numdam.org/articles/10.1051/ita:2003014/

Bibliographie
Cité par

[1] R. Aharoni and N. Linial, Minimal non 2-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A 43 (1986). | MR | Zbl

[2] B. Aspvall, M.F. Plass and R.E. Tarjan, A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8 (1979) 121-123. | MR | Zbl

[3] B. Bollobás, Random graphs. Academic Press (1985). | MR | Zbl

[4] V. Chvátal, Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Algorithms 2 (1991) 11-28. | MR | Zbl

[5] V. Chvátal and B. Reed, Mick gets some (the odds are on his side), in Proc. of the 33rd Annual Symposium on Foundations of Computer Science. IEEE (1992) 620-627. | Zbl

[6] N. Creignou and H. Daudé, Satisfiability threshold for random XOR-CNF formulæ. Discrete Appl. Math. 96-97 (1999) 41-53. | MR | Zbl

[7] O. Dubois, Y. Boufkhad and J. Mandler, Typical random 3-SAT formulae and the satisfiability threshold, in Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms, SODA'2000 (2000) 124-126. | Zbl

[8] P. Erdös and A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 7 (1960) 17-61. | MR | Zbl

[9] E. Friedgut and an Appendix by J. Bourgain, Sharp thresholds of graph properties, and the $k$ -sat problem. J. Amer. Math. Soc. 12 (1999) 1017-1054. | MR | Zbl

[10] A. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms 20 (1996) 312-355. | MR | Zbl

[11] I.P. Gent and T. Walsh, The SAT phase transition, in Proc. of the 11th European Conference on Artificial Intelligence (1994) 105-109.

[12] A. Goerdt, A threshold for unsatisfiability. J. Comput. System Sci. 53 (1996) 469-486. | MR | Zbl

[13] G. Grimmet, Percolation. Springer Verlag (1989). | Zbl

[14] S. Janson, Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl. 26 (1987) 1-30. | MR | Zbl

[15] S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions. Science 264 (1994) 1297-1301. | MR

[16] V.F. Kolchin, Random graphs and systems of linear equations in finite fields. Random Struct. Algorithms 5 (1995) 425-436. | MR | Zbl

[17] V.F. Kolchin, Random graphs. Cambridge University Press (1999). | MR | Zbl

[18] V.F. Kolchin and V.I. Khokhlov, A threshold effect for systems of random equations of a special form. Discrete Math. Appl. 2 (1992) 563-570. | MR | Zbl

[19] I.N. Kovalenko, On the limit distribution of the number of solutions of a random system of linear equations in the class of boolean functions. Theory Probab. Appl. 12 (1967) 47-56. | MR | Zbl

[20] D. Mitchell, B. Selman and H. Levesque, Hard and easy distributions of SAT problems, in Proc. of the 10th National Conference on Artificial Intelligence (1992) 459-465.

[21] R. Monasson and R. Zecchina, Statistical mechanics of the random K-sat model. Phys. Rev. E 56 (1997) 1357. | MR

[22] T.J. Schaefer, The complexity of satisfiability problems, in Proceedings 10th STOC, San Diego (CA, USA). Association for Computing Machinery (1978) 216-226. | MR

[23] L. Takács, On the limit distribution of the number of cycles in a random graph. J. Appl. Probab. 25 (1988) 359-376. | MR | Zbl

Cité par Sources :