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

Nadia Creignou; Hervé Daudé

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 37.2 (2010): 127-147. <http://eudml.org/doc/92718>.

@article{Creignou2010,
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 ≥ 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},
keywords = {Threshold phenomenon; satisfiability; phase transition; random Boolean linear systems.; threshold phenomenon},
language = {eng},
month = {3},
number = {2},
pages = {127-147},
publisher = {EDP Sciences},
title = {Smooth and sharp thresholds for random \{k\}-XOR-CNF satisfiability},
url = {http://eudml.org/doc/92718},
volume = {37},
year = {2010},
}

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
DA - 2010/3//
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 ≥ 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
UR - http://eudml.org/doc/92718
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.05045
  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.68042
  3. B. Bollobás, Random graphs. Academic Press (1985).  Zbl0567.05042
  4. V. Chvátal, Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Algorithms2 (1991) 11-28.  Zbl0715.05026
  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.68151
  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.16301
  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.  Zbl0932.05084
  10. A. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms20 (1996) 312-355.  Zbl0852.68038
  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.68077
  13. G. Grimmet, Percolation. Springer Verlag (1989).  
  14. S. Janson, Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl.26 (1987) 1-30.  Zbl0633.60070
  15. S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions. Science264 (1994) 1297-1301.  Zbl1226.68097
  16. V.F. Kolchin, Random graphs and systems of linear equations in finite fields. Random Struct. Algorithms5 (1995) 425-436.  Zbl0867.60037
  17. V.F. Kolchin, Random graphs. Cambridge University Press (1999).  Zbl0918.05001
  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.05073
  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.  
  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. E56 (1997) 1357.  Zbl0942.68052
  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.68143
  23. L. Takács, On the limit distribution of the number of cycles in a random graph. J. Appl. Probab.25 (1988) 359-376.  

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.