Abstract
As $n$ tends to infinity, the probability of satisfiability for a random 2-SAT formula on $n$ variables, where each clause occurs independently with probability $\alpha/2n$, exhibits a sharp threshold at $\alpha=1$. We study a more general 2-SAT model in which each clause occurs independently but with probability $\alpha_i/2n$ where $i \in \{0,1,2\}$ is the number of positive literals in that clause. We generalize branching process arguments by Verhoeven (1999) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.
Introduction
The 2-Satisfiability (2-SAT) problem is a cornerstone of computational complexity and discrete mathematics. While the general $k$-SAT problem is NP-complete for $k \ge 3$, 2-SAT is solvable in polynomial time. A fascinating property of random 2-SAT instances is the existence of a phase transition: as the ratio of clauses to variables increases, the formula shifts abruptly from being almost certainly satisfiable to almost certainly unsatisfiable.
In the standard Erdős-Rényi style model for random 2-SAT, every possible clause is included with equal probability. This leads to a well-known threshold at $\alpha = 1$. However, real-world constraints often exhibit non-uniform distributions. This paper by Elchanan Mossel and Arnab Sen investigates a generalized model where the probability of a clause depends on the number of positive literals it contains, providing a more nuanced understanding of the phase transition through the lens of branching processes.
The Generalized 2-SAT Model
The authors consider a formula on $n$ variables where each possible 2-clause is included independently. The clauses are categorized by the number of positive literals $i \in \{0, 1, 2\}$:
- Type 0: $(\neg x \lor \neg y)$
- Type 1: $(x \lor \neg y)$ or $(\neg x \lor y)$
- Type 2: $(x \lor y)$
Each clause of type $i$ is present with probability $\alpha_i / 2n$. This generalization allows for the modeling of systems where, for example, negative constraints are more frequent than positive ones, a scenario common in statistical physics and discrete optimization.
Methodology: Implication Digraphs and Branching Processes
To analyze satisfiability, the authors utilize the implication digraph. Any 2-SAT clause $(l_1 \lor l_2)$ can be written as two directed implications: $(\neg l_1 \to l_2)$ and $(\neg l_2 \to l_1)$. A formula is unsatisfiable if and only if there exists a variable $x$ such that there is a path from $x$ to $\neg x$ and a path from $\neg x$ back to $x$ in this digraph.
The key innovation lies in modeling the exploration of these paths as a multi-type branching process. When we follow an implication from a literal, the "children" in the branching process are the literals implied by the current one. Because there are two types of literals (positive $x$ and negative $ eg x$), this is a 2-type branching process. The authors rely on the fact that in large random graphs, the local neighborhood of any point is "tree-like," allowing branching processes to accurately describe global behavior.
The growth of this process is governed by a $2 \times 2$ branching matrix $M$: $$M = \frac{1}{2} \begin{pmatrix} \alpha_1 & \alpha_0 \\ \alpha_2 & \alpha_1 \end{pmatrix}$$ In this matrix, the entries represent the expected number of literals of a certain type implied by a literal of a given type.
The Spectral Threshold
The central result of the paper is that the satisfiability threshold is determined by the maximum eigenvalue (spectral radius) $\rho$ of the matrix $M$. The authors prove that: $$\rho = \frac{\alpha_1 + \sqrt{\alpha_0 \alpha_2}}{2}$$
Theorem 1 (The Phase Transition)
- Satisfiable Regime: If $\rho < 1$, the probability that the formula is satisfiable tends to 1 as $n \to \infty$.
- Unsatisfiable Regime: If $\rho > 1$, the probability that the formula is satisfiable tends to 0 as $n \to \infty$.
This result is intuitive from the perspective of branching processes: if the expected number of "descendants" (implied literals) is less than 1, the process dies out quickly, and the likelihood of forming a contradictory cycle is negligible. If the expected number is greater than 1, the process "explodes," making the existence of a contradiction almost certain in a large graph. This is simplified further through the concept of "hooked chains," which are sequences of implications leading to contradictions.
Discussion and Limitations
This work extends the classic result by Verhoeven (1999) and provides a rigorous foundation for non-uniform 2-SAT models. By showing that the threshold is purely a function of the spectral radius of the branching matrix, the authors provide a powerful tool for analyzing complex logical systems.
However, several limitations remain:
- Specific to 2-SAT: The implication digraph method is unique to 2-SAT. For $k \ge 3$, the relationship between clauses and implications is not as straightforward, and branching processes alone are insufficient to locate the exact threshold.
- Variable Degrees: The model is based on clause types and is currently "incomparable" to models based on literal degrees (the frequency of specific variables). A unified theory remains an open challenge.
- The Scaling Window: The paper identifies the threshold but does not explore the narrow range of values right at $\rho = 1$ where the system's behavior is most chaotic.
Summary updated