Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T19:25:57.325Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 November 2003

Nadia Creignou  and
Hervé Daudé
Nadia Creignou
Affiliation:
LIF, UMR 6166 du CNRS, Université de la Méditerranée, 163, avenue de Luminy, 13288 Marseille, France; [email protected].
Hervé Daudé
Affiliation:
LATP, UMR 6632 du CNRS, Université de Provence, 39 rue Joliot-Curie, 13453 Marseille, France; [email protected].
Get access

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.

Keywords

Threshold phenomenonsatisfiabilityphase transitionrandomBoolean linear systems.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 37 , Issue 2 , April 2003 , pp. 127 - 147
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

R. Aharoni and N. Linial, Minimal non 2-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A 43 (1986).
Aspvall, B., Plass, M.F. and Tarjan, R.E., A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8 (1979) 121-123. CrossRef
B. Bollobás, Random graphs. Academic Press (1985).
Chvátal, V., Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Algorithms 2 (1991) 11-28. CrossRef
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.
Creignou, N. and Daudé, H., Satisfiability threshold for random XOR-CNF formulæ. Discrete Appl. Math. 96-97 (1999) 41-53. CrossRef
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.
Erdös, P. and Rényi, A., On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 7 (1960) 17-61.
Friedgut, E. and an Appendix by J. Bourgain, Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc. 12 (1999) 1017-1054. CrossRef
Frieze, A. and Suen, S., Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms 20 (1996) 312-355. CrossRef
I.P. Gent and T. Walsh, The SAT phase transition, in Proc. of the 11th European Conference on Artificial Intelligence (1994) 105-109.
Goerdt, A., A threshold for unsatisfiability. J. Comput. System Sci. 53 (1996) 469-486. CrossRef
G. Grimmet, Percolation. Springer Verlag (1989).
Janson, S., Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl. 26 (1987) 1-30. CrossRef
Kirkpatrick, S. and Selman, B., Critical behavior in the satisfiability of random Boolean expressions. Science 264 (1994) 1297-1301. CrossRef
Kolchin, V.F., Random graphs and systems of linear equations in finite fields. Random Struct. Algorithms 5 (1995) 425-436.
V.F. Kolchin, Random graphs. Cambridge University Press (1999).
Kolchin, V.F. and Khokhlov, V.I., A threshold effect for systems of random equations of a special form. Discrete Math. Appl. 2 (1992) 563-570. CrossRef
Kovalenko, I.N., 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. CrossRef
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.
Monasson, R. and Zecchina, R., Statistical mechanics of the random K-sat model. Phys. Rev. E 56 (1997) 1357. CrossRef
T.J. Schaefer, The complexity of satisfiability problems, in Proceedings 10th STOC, San Diego (CA, USA). Association for Computing Machinery (1978) 216-226.
Takács, L., On the limit distribution of the number of cycles in a random graph. J. Appl. Probab. 25 (1988) 359-376. CrossRef