Smooth and sharp thresholds for random {k}-XOR-CNF satisfiability
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 37, Issue: 2, page 127-147
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topCreignou, 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- R. Aharoni and N. Linial, Minimal non 2-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A 43 (1986).
- 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.
- B. Bollobás, Random graphs. Academic Press (1985).
- V. Chvátal, Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Algorithms2 (1991) 11-28.
- 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.
- N. Creignou and H. Daudé, Satisfiability threshold for random XOR-CNF formulæ. Discrete Appl. Math.96-97 (1999) 41-53.
- 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.
- P. Erdös and A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci.7 (1960) 17-61.
- 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.
- A. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms20 (1996) 312-355.
- I.P. Gent and T. Walsh, The SAT phase transition, in Proc. of the 11th European Conference on Artificial Intelligence (1994) 105-109.
- A. Goerdt, A threshold for unsatisfiability. J. Comput. System Sci.53 (1996) 469-486.
- G. Grimmet, Percolation. Springer Verlag (1989).
- S. Janson, Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl.26 (1987) 1-30.
- S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions. Science264 (1994) 1297-1301.
- V.F. Kolchin, Random graphs and systems of linear equations in finite fields. Random Struct. Algorithms5 (1995) 425-436.
- V.F. Kolchin, Random graphs. Cambridge University Press (1999).
- 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.
- 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.
- 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.
- R. Monasson and R. Zecchina, Statistical mechanics of the random K-sat model. Phys. Rev. E56 (1997) 1357.
- T.J. Schaefer, The complexity of satisfiability problems, in Proceedings 10th STOC, San Diego (CA, USA). Association for Computing Machinery (1978) 216-226.
- L. Takács, On the limit distribution of the number of cycles in a random graph. J. Appl. Probab.25 (1988) 359-376.
NotesEmbed ?
topYou 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.