Percolation and Phase Transition in SAT
share
Erdös and Rényi proved in 1960 that a drastic change occurs in a large random graph when the number of edges is half the number of nodes: a giant connected component surges. This was the origin of percolation theory, where statistic mechanics and mean field techniques are applied to study the behavior of graphs and other structures when we remove edges randomly. In the 90's the study of random SAT instances started. It was proved that in large 2-SAT random instances also a drastic change occurs when the number of clauses is equal to the number of variables: the formula almost surely changes from satisfiable to unsatisfiable. The same effect, but at distinct clause/variable ratios, was detected in k-SAT and other random models. In this paper we study the relation between both phenomena, and establish a condition that allows us to easily find the phase transition threshold in several models of 2-SAT formulas. In particular, we prove the existence of a phase transition threshold in scale-free random 2-SAT formulas.
READ FULL TEXT