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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

- Volume: 37, Issue: 2, page 127-147
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCreignou, Nadia, and Daudé, Hervé. "Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.2 (2003): 127-147. <http://eudml.org/doc/245877>.

@article{Creignou2003,

abstract = {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\ge 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$.},

author = {Creignou, Nadia, Daudé, Hervé},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {threshold phenomenon; satisfiability; phase transition; random boolean linear systems; Threshold phenomenon; random Boolean linear systems},

language = {eng},

number = {2},

pages = {127-147},

publisher = {EDP-Sciences},

title = {Smooth and sharp thresholds for random $\{k\}$-XOR-CNF satisfiability},

url = {http://eudml.org/doc/245877},

volume = {37},

year = {2003},

}

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

PB - EDP-Sciences

VL - 37

IS - 2

SP - 127

EP - 147

AB - 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\ge 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$.

LA - eng

KW - threshold phenomenon; satisfiability; phase transition; random boolean linear systems; Threshold phenomenon; random Boolean linear systems

UR - http://eudml.org/doc/245877

ER -

## References

top- [1] R. Aharoni and N. Linial, Minimal non 2-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A 43 (1986). Zbl0611.05045MR867645
- [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. Zbl0398.68042MR526451
- [3] B. Bollobás, Random graphs. Academic Press (1985). Zbl0567.05042MR809996
- [4] V. Chvátal, Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Algorithms 2 (1991) 11-28. Zbl0715.05026MR1099577
- [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. Zbl0977.68538
- [6] N. Creignou and H. Daudé, Satisfiability threshold for random XOR-CNF formulæ. Discrete Appl. Math. 96-97 (1999) 41-53. Zbl0941.68151MR1724715
- [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. Zbl0959.68135
- [8] P. Erdös and A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 7 (1960) 17-61. Zbl0103.16301MR125031
- [9] E. Friedgutand an Appendix by J. Bourgain, Sharp thresholds of graph properties, and the $k$-sat problem. J. Amer. Math. Soc. 12 (1999) 1017-1054. Zbl0932.05084MR1678031
- [10] A. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms 20 (1996) 312-355. Zbl0852.68038MR1379227
- [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. Zbl0870.68077MR1423858
- [13] G. Grimmet, Percolation. Springer Verlag (1989). Zbl0691.60089
- [14] S. Janson, Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl. 26 (1987) 1-30. Zbl0633.60070MR917244
- [15] S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions. Science 264 (1994) 1297-1301. Zbl1226.68097MR1275579
- [16] V.F. Kolchin, Random graphs and systems of linear equations in finite fields. Random Struct. Algorithms 5 (1995) 425-436. Zbl0795.05128MR1248181
- [17] V.F. Kolchin, Random graphs. Cambridge University Press (1999). Zbl0918.05001MR1728076
- [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. Zbl0787.05073MR1138095
- [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. Zbl0201.51002MR219119
- [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. Zbl0942.68052MR1464158
- [22] T.J. Schaefer, The complexity of satisfiability problems, in Proceedings 10th STOC, San Diego (CA, USA). Association for Computing Machinery (1978) 216-226. Zbl1282.68143MR521057
- [23] L. Takács, On the limit distribution of the number of cycles in a random graph. J. Appl. Probab. 25 (1988) 359-376. Zbl0662.60017MR974594

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.