Abstract
It is well known that, as $n$ tends to $\infty$, 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 the branching process arguments used by Verhoeven (1999) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.
Introduction
In the study of random Boolean formulas, the 2-SAT problem represents a fundamental boundary between tractability and complexity. While 2-SAT is solvable in polynomial time, its behavior in a random setting reveals a fascinating "phase transition." As the density of clauses increases, the probability that a formula is satisfiable drops abruptly from nearly 1 to nearly 0. In the standard model, where every possible clause is equally likely, this threshold is well-established at $\alpha = 1$.
However, real-world logical systems often exhibit imbalances—certain variables may appear more frequently in their positive form than their negative form. Researchers Elchanan Mossel and Arnab Sen address this by generalizing the 2-SAT model to account for the distribution of positive and negative literals within clauses. By employing the theory of multitype branching processes, they provide a rigorous framework for determining the satisfiability threshold in these non-uniform environments.
The Generalized 2-SAT Model
In this generalized model, we consider $n$ variables. A clause can contain zero, one, or two positive literals. The probability of any specific clause appearing in the formula is defined as:
- $\alpha_0 / 2n$ for clauses with zero positive literals (e.g., $\neg x \lor \neg y$)
- $\alpha_1 / 2n$ for clauses with one positive literal (e.g., $x \lor \neg y$)
- $\alpha_2 / 2n$ for clauses with two positive literals (e.g., $x \lor y$)
This distinction allows for the modeling of systems where constraints are biased toward certain truth assignments, a common occurrence in practical applications of logic and constraint satisfaction.
Methodology: Implication Digraphs and Branching
The authors utilize the logical equivalence between a 2-SAT clause $(u \lor v)$ and the implications $(\neg u \to v)$ and $(\neg v \to u)$. This allows a random formula to be represented as an implication digraph. 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$ (a contradictory cycle).
To analyze the likelihood of such cycles, the authors model the paths of implications as a multitype branching process. Starting from a single literal, the "offspring" are the literals it implies through the random clauses. Because the probabilities $\alpha_0, \alpha_1, \alpha_2$ differ, the "type" of the literal (positive or negative) determines the expected number and type of its children.
The Branching Matrix
The dynamics of this process are captured 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 another type. The critical value for the survival of this "family tree" of implications is the spectral radius (the largest eigenvalue, $\rho$) of $M$.
Key Results
The central contribution of this work is the formalization of Theorem 1, which identifies the sharp threshold for satisfiability based on the spectral radius $\rho$:
$$\rho = \frac{\alpha_1 + \sqrt{\alpha_0 \alpha_2}}{2}$$
- The Satisfiable Regime: If $\rho < 1$, the probability that a random formula is satisfiable tends to 1 as $n \to \infty$. In this regime, the implication chains die out quickly, making the formation of contradictory cycles highly improbable.
- The Unsatisfiable Regime: If $\rho > 1$ (and $\alpha_0 \alpha_2 > 0$), the probability of satisfiability tends to 0. Here, the implication chains grow large enough to inevitably intersect and form contradictions.
This result generalizes the classic 2-SAT threshold. If we set $\alpha_0 = \alpha_1 = \alpha_2 = \alpha$, the formula simplifies to $\rho = \alpha$, recovering the standard threshold of $\alpha = 1$.
Discussion and Insights
The use of the spectral radius highlights a non-linear relationship in the threshold. The interaction between purely negative clauses ($\alpha_0$) and purely positive clauses ($\alpha_2$) is captured by the geometric mean $\sqrt{\alpha_0 \alpha_2}$, suggesting that the balance between these two types is as critical as their individual densities.
While this branching process approach provides a clean solution for 2-SAT, the authors note that $k$-SAT (for $k \ge 3$) remains a significantly more difficult challenge. Unlike 2-SAT, $k$-SAT does not have a simple implication graph structure, preventing a direct application of these branching process tools. Furthermore, the current study focuses on the regimes strictly above or below the threshold; the "critical window" where $\rho \approx 1$ remains an open area for further probabilistic investigation.
Summary updated