Geodesic
Smooth and sharp thresholds for random k-XOR-CNF satisfiability
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 127-147 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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.

DOI : 10.1051/ita:2003014
Classification : 05C80, 68R05, 60C05
Keywords: threshold phenomenon, satisfiability, phase transition, random boolean linear systems 
@article{ITA_2003__37_2_127_0,
     author = {Creignou, Nadia and Daud\'e, Herv\'e},
     title = {Smooth and sharp thresholds for random ${k}${-XOR-CNF} satisfiability},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {127--147},
     year = {2003},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {2},
     doi = {10.1051/ita:2003014},
     mrnumber = {2015688},
     zbl = {1112.68390},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2003014/}
}
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
SP  - 127
EP  - 147
VL  - 37
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2003014/
DO  - 10.1051/ita:2003014
LA  - en
ID  - ITA_2003__37_2_127_0
ER  - 
%0 Journal Article
%A Creignou, Nadia
%A Daudé, Hervé
%T Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2003
%P 127-147
%V 37
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2003014/
%R 10.1051/ita:2003014
%G en
%F ITA_2003__37_2_127_0
Creignou, Nadia; Daudé, Hervé. Smooth and sharp thresholds for random ${k}$-XOR-CNF satisfiability. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 127-147. doi: 10.1051/ita:2003014

Cité par Sources :