# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas  
[PERSON] and [PERSON] [35] proved that a random formula with \((1+o(1))cn\) clauses of size 2 over \(n\) variables is satisfiable with probability \(1-o(1)\), when \(c<1\), and unsatisfiable with probability \(1-o(1)\), when \(c>1\), where \(o(1)\) represents a quantity tending to zero as \(n\) tends to infinity. As we will see in this section, a similar result for scale-free random 2-SAT formulas can be obtained using percolation and mean-field techniques. Percolation theory describes the behavior of connected components in a graph when we remove edges randomly. [PERSON] and [PERSON] [36] are considered the initiators of this theory. In this seminal paper on graph theory, they proposed a random graph model \(G(n,m)\) where all graphs with \(n\) nodes and \(m\) edges are selected with the same probability. [PERSON] [37] proposed a similar model \(G(n,p)\) where \(n\) is also the number of nodes, and every \(\binom{n}{2}\) possible edge is selected with probability \(p\). For not very sparse graphs (when \(p\,n^{2}\to\infty\)), both models have basically the same properties, taking \(m=\binom{n}{2}p\). [PERSON] and [PERSON] [38] also studied the connectivity on these graphs and proved that  
* when \(n\,p<1\), i.e., \(m<n/2\), a random graph almost surely has no connected component larger than \(\mathcal{O}(\log n)\);
* when \(n\,p=1\), i.e., \(m=n/2\) a largest component of size \(n^{2/3}\) almost surely emerges;
* when \(n\,p>1\), i.e., \(m>n/2\), the graph almost surely contains a unique giant component with a fraction of the nodes and no other component contains more than \(\mathcal{O}(\log n)\) nodes. Phase transition is a phenomenon that has been observed and studied in many AI problems. Many problems have an order parameter that separates a region of solvable and unsolvable problems, and it has been observed that hard problems occur at critical values of this parameter. [PERSON] et al. [39] found this phenomenon in 3-SAT when the ratio between the number of clauses and variables is \(m/n\approx 4.3\). [PERSON] and [PERSON] [40] observed the same phenomenon with clauses of mixed length. There is a close relationship between SAT problems and graphs. Both, percolation on graphs and phase transition in SAT (or other AI problems) are critical phenomena and both can be studied using mean-field techniques from statistical mechanics. Percolation theory has been used and inspired works in the literature about random SAT and satisfiability threshold, e.g., in [PERSON] et al. [41], to determine the satisfiability threshold of 1-in-k SAT and NAE 3-SAT formulas. Some results on graphs have been previously extended to 2-SAT. For instance, [PERSON] and [PERSON] [42] adapted Achlioptas processes for graphs into formulas. [PERSON] et al. [43] investigated the scaling window of the 2-SAT phase transition, finding the critical exponent of the order parameter and proving that the transition is continuous, adapting results of [PERSON] [44] for Erdos-Renyi graphs. The relationship between percolation in random graphs and phase transition in random 2-SAT formulas is suggested in many other works. For instance, [PERSON] et al. [45] when studying the phase transition in \(2+P\)-SAT (a mixture of \((1-p)m\) clauses of size 2 and \(p\,m\) clauses of size 3) mentioned that _\"It is likely that the 2 SAT transition results from percolation of these loops...\"_. [PERSON] et al. [17] use the emergence of a giant component in a graph to prove the existence of a phase transition in 2-SAT random formulas with prescribed degrees, using the configuration model. They find, for this model, the same criterion as [PERSON] et al. [12] and us in Theorem 2. Given a random 2-SAT formula with \(m\) clauses over \(n\) variables, we can construct an Erdos-Renyi graph where the \(2\,n\) literals are nodes, and the \(m\) clauses are edges. At the percolation point \(m=(2\,n)/2\) of this graph, a _giant component_ emerges. Just at the same point \(m=n\), the 2-SAT phase transition threshold is located.