Exact location of the phase transition for random (1,2)-QSAT

Creignou, Nadia; Daudé, Hervé; Egly, Uwe; Rossignol, Raphaël

doi:10.1051/ita/2014025

Creignou, Nadia ¹ ; Daudé, Hervé ² ; Egly, Uwe ³ ; Rossignol, Raphaël ^4,⁵

¹ Aix-Marseille Université, CNRS, LIF UMR 7279, 13288 Marseille, France
² Aix-Marseille Université, CNRS, I2M UMR 7373, 13453 Marseille, France
³ Institut für Informationsysteme 184/3, Technische Universität Wien, Favoritenstrasse 9-11 A-1040 Wien, Austria
⁴ University Grenoble Alpes, IF, 38000 Grenoble, France
⁵ CNRS, IF, 38000 Grenoble, France

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 1, pp. 23-45 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

Résumé

The $Q S A T$ problem is the quantified version of the $S A T$ problem. We show the existence of a threshold effect for the phase transition associated with the satisfiability of random quantified boolean CNF formulas of the form $\forall X \exists Y ϕ (X, Y)$ , where $X$ has $m$ variables, $Y$ has $n$ variables and each clause in $ϕ$ has one literal from $X$ and two from $Y$ . For such formulas, we show that the threshold phenomenon is controlled by the ratio between the number of clauses and the number $n$ of existential variables. Then we give the exact location of the associated critical ratio $c^{*}$ : it is a decreasing function of $α$ , where $α$ is the limiting value of $m / l o g (n)$ when $n$ tends to infinity. Thus we give a precise location of the phase transition associated with a $c o N P$ -complete problem.

Reçu le : 2014-05-05
Accepté le : 2014-08-28

MR Zbl

DOI : 10.1051/ita/2014025

Classification : 68R01, 60C05, 05A16
Keywords: Random quantified formulas, satisfiability, phase transition, sharp threshold

Affiliations des auteurs :

Creignou, Nadia ¹ ; Daudé, Hervé ² ; Egly, Uwe ³ ; Rossignol, Raphaël ^{4, 5}

¹ Aix-Marseille Université, CNRS, LIF UMR 7279, 13288 Marseille, France
² Aix-Marseille Université, CNRS, I2M UMR 7373, 13453 Marseille, France
³ Institut für Informationsysteme 184/3, Technische Universität Wien, Favoritenstrasse 9-11 A-1040 Wien, Austria
⁴ University Grenoble Alpes, IF, 38000 Grenoble, France
⁵ CNRS, IF, 38000 Grenoble, France

@article{ITA_2015__49_1_23_0,
     author = {Creignou, Nadia and Daud\'e, Herv\'e and Egly, Uwe and Rossignol, Rapha\"el},
     title = {Exact location of the phase transition for random {(1,2)-QSAT}},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {23--45},
     year = {2015},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {1},
     doi = {10.1051/ita/2014025},
     mrnumber = {3342171},
     zbl = {1327.68129},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2014025/}
}

TY  - JOUR
AU  - Creignou, Nadia
AU  - Daudé, Hervé
AU  - Egly, Uwe
AU  - Rossignol, Raphaël
TI  - Exact location of the phase transition for random (1,2)-QSAT
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2015
SP  - 23
EP  - 45
VL  - 49
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2014025/
DO  - 10.1051/ita/2014025
LA  - en
ID  - ITA_2015__49_1_23_0
ER  -

%0 Journal Article
%A Creignou, Nadia
%A Daudé, Hervé
%A Egly, Uwe
%A Rossignol, Raphaël
%T Exact location of the phase transition for random (1,2)-QSAT
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2015
%P 23-45
%V 49
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2014025/
%R 10.1051/ita/2014025
%G en
%F ITA_2015__49_1_23_0

Creignou, Nadia; Daudé, Hervé; Egly, Uwe; Rossignol, Raphaël. Exact location of the phase transition for random (1,2)-QSAT. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 1, pp. 23-45. doi: 10.1051/ita/2014025

Cité par Sources :

Parcourir par

Geodesic

Parcourir par