Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- 1 April 2003
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 37 (2) , 127-147
- https://doi.org/10.1051/ita:2003014
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
This publication has 16 references indexed in Scilit:
- Satisfiability threshold for random XOR-CNF formulasDiscrete Applied Mathematics, 1999
- Sharp thresholds of graph properties, and the $k$-sat problemJournal of the American Mathematical Society, 1999
- A Threshold for UnsatisfiabilityJournal of Computer and System Sciences, 1996
- Analysis of Two Simple Heuristics on a Random Instance ofk-satJournal of Algorithms, 1996
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994
- On the number of cycles in a random non-equiprobable graphDiscrete Mathematics and Applications, 1992
- Almost all graphs with 1.44n edges are 3‐colorableRandom Structures & Algorithms, 1991
- Poisson convergence and poisson processes with applications to random graphsStochastic Processes and their Applications, 1987
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulasJournal of Combinatorial Theory, Series A, 1986
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979