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

Nadia Creignou; Hervé Daudé

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

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

Abstract

top
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 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 .

How to cite

top

Creignou, 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. [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. [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. [3] B. Bollobás, Random graphs. Academic Press (1985). Zbl0567.05042MR809996
  4. [4] V. Chvátal, Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Algorithms 2 (1991) 11-28. Zbl0715.05026MR1099577
  5. [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. [6] N. Creignou and H. Daudé, Satisfiability threshold for random XOR-CNF formulæ. Discrete Appl. Math. 96-97 (1999) 41-53. Zbl0941.68151MR1724715
  7. [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. [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. [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. [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. [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. [12] A. Goerdt, A threshold for unsatisfiability. J. Comput. System Sci. 53 (1996) 469-486. Zbl0870.68077MR1423858
  13. [13] G. Grimmet, Percolation. Springer Verlag (1989). Zbl0691.60089
  14. [14] S. Janson, Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl. 26 (1987) 1-30. Zbl0633.60070MR917244
  15. [15] S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions. Science 264 (1994) 1297-1301. Zbl1226.68097MR1275579
  16. [16] V.F. Kolchin, Random graphs and systems of linear equations in finite fields. Random Struct. Algorithms 5 (1995) 425-436. Zbl0795.05128MR1248181
  17. [17] V.F. Kolchin, Random graphs. Cambridge University Press (1999). Zbl0918.05001MR1728076
  18. [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. [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. [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. [21] R. Monasson and R. Zecchina, Statistical mechanics of the random K-sat model. Phys. Rev. E 56 (1997) 1357. Zbl0942.68052MR1464158
  22. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.