caa a22 4500 445804769 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00453-009-9308-1 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9308-1 Random 2 XORSAT Phase Transition [Elektronische Daten] [Daudé Hervé, Ravelomanana Vlady] We consider the 2-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form x ⊕ y=0 or x ⊕ y=1. Formula of size m on n Boolean variables are chosen uniformly at random from among all ${n(n-1)\choose m}$ possible choices. When c<1/2 and as n tends to infinity, the probability p(n,m=cn) that a random 2-XOR formula is satisfiable, tends to the threshold function exp (c/2)⋅(1−2c)1/4. This gives the asymptotic behavior of random 2-XOR formula in the SAT/UNSAT subcritical phase transition. In this paper, we first prove that the error term in this subcritical region is O(n −1). Then, in the critical region c=1/2, we prove that p(n,n/2)=Θ(n −1/12). Our study relies on the symbolic method and analytical tools coming from generating function theory which also enable us to describe the evolution of $n^{1/12}\ p(n,\frac{n}{2}(1+\mu n^{-1/3}))$ as a function of μ. Thus, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of 2-XORSAT transition. Springer Science+Business Media, LLC, 2009 XORSAT nationallicence Satisfiability nationallicence Constraint Satisfaction Problem nationallicence Phase transition nationallicence Random graph nationallicence Generating functions nationallicence Finite size scaling nationallicence Hervé Daudé Laboratoire d'Analyse, Topologie et Probabilités, UMR CNRS 6632, Université de Provence, 39, rue Joliot Curie, 13453, Marseille Cedex 13, France aut Vlady Ravelomanana Laboratoire d'informatique de Paris Nord, UMR CNRS 7030, Institut Galilée, Université Paris Nord, 99, Av. Clément, 93430, Villetaneuse, France aut Algorithmica Springer-Verlag 59/1(2011-01-01), 48-65 0178-4617 59:1<48 2011 59 453 https://doi.org/10.1007/s00453-009-9308-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9308-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hervé Daudé Laboratoire d'Analyse, Topologie et Probabilités, UMR CNRS 6632, Université de Provence, 39, rue Joliot Curie, 13453, Marseille Cedex 13, France aut NATIONALLICENCE 700 1- Vlady Ravelomanana Laboratoire d'informatique de Paris Nord, UMR CNRS 7030, Institut Galilée, Université Paris Nord, 99, Av. Clément, 93430, Villetaneuse, France aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/1(2011-01-01), 48-65 0178-4617 59:1<48 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer