Abstract
Whether a clause has $2$ or $3$ literals looks like a small difference. This paper measures the share of satisfiable random formulas and the work to solve them, and counts that the difference shows in two places: where the cliff lies and how the work grows. No new theorem or law is claimed.
First, both solvers are correct: $200$ 2-SAT problems solved with the implication graph and $100$ 3-SAT problems solved by branching agreed with trying all assignments (Section 2).
Second, the 2-SAT cliff sharpens between $\alpha=1$ and $1.5$: at $\alpha=1.5$ the share falls from $0.695$ with $20$ variables to $0.025$ with $320$, while at $\alpha=1.0$ it drops slowly: $0.975$, $0.960$, $0.945$ (Section 2).
Third, the 3-SAT cliff lies further right: with $20$ variables, the share is $0.850$ at $\alpha=4.0$, $0.650$ at $4.25$, $0.583$ at $4.5$ and $0.283$ at $5.0$ (Section 2).
Fourth, and this is the core. The work near the cliff grows differently: doubling the variables from $20$ to $40$ with the same branching solver multiplies the mean branches by $\mathbf{3.377358}$ for 3-SAT and by $\mathbf{1.536885}$ for 2-SAT (Section 3).
Fifth, 2-SAT work grows slower than the variables, 3-SAT faster: 2-SAT branches grow $4.569672$-fold for $8$ times the variables; 3-SAT grows $7.347015$-fold for $4$ times (Section 3).
Sixth, the separator is whether one looks at the share satisfiable or at the branches needed to solve: both have a cliff, but the work jumps on the cliff only when clauses have three literals (Section 4).
Keywords: satisfiability problem, 2-SAT, 3-SAT, implication graph, branching, cliff.
Scope (what is not claimed)
No new theorem or law is claimed: that 2-SAT is solved quickly via strongly connected components of the implication graph, that 3-SAT counts among the generally hard problems, and that the share of satisfiable random formulas collapses near some clause ratio, are all known. Complexity theory is not entered: the relation of P and NP and proofs of hardness are not entered. No theoretical cliff position is claimed: only shares for small formulas were measured, up to $320$ variables ($40$ for 3-SAT); the limiting position as variables grow is not stated. Fast solvers are not discussed: the branching solver is a tool for counting work; good solvers are not compared. Relation to earlier papers: Paper 348 showed that on the same graph, connecting is cheap and ordering is not. This paper stands beside it. There, two questions on the same graph split the work. Here, formulas of the same form split how the work grows depending only on whether clauses have two or three literals. What is added is checking both solvers against all assignments, measuring how the cliff sharpens with more variables, measuring the work factors $3.377358$ and $1.536885$ for doubled variables with the same solver, and placing the separator on share satisfiable versus branches.
1. Notation and the Question
Setting: random formulas with $n$ variables and $m$ clauses are built. Each clause picks $k$ distinct variables, negates each with probability one half, and joins them with “or”. The formula joins the clauses with “and”.
$$\alpha=\frac{m}{n},\qquad \text{2-SAT}:\ k=2,\qquad \text{3-SAT}:\ k=3$$2-SAT was solved with strongly connected components of the implication graph, and 3-SAT by settling clauses with one remaining literal first and then splitting on the most frequent variable (branching). Work was counted as the number of times the splitting step was called (branches).
Question: what changes between two and three literals per clause?
2. The Cliff of the Share Satisfiable
Computation 2.1: $200$ 2-SAT problems were solved for each setting and the share satisfiable computed.
| variables | $\alpha=0.5$ | $0.8$ | $1.0$ | $1.2$ | $1.5$ | $2.0$ |
|---|---|---|---|---|---|---|
| $20$ | $1.000$ | $0.985$ | $0.975$ | $0.915$ | $0.695$ | $0.245$ |
| $80$ | $1.000$ | $0.995$ | $0.960$ | $0.800$ | $0.345$ | $0.005$ |
| $320$ | $1.000$ | $1.000$ | $0.945$ | $0.625$ | $0.025$ | $0.000$ |
Computation 2.2: $60$ 3-SAT problems were solved for each setting; the share satisfiable and the median branches (in parentheses) are shown.
| variables | $\alpha=3.0$ | $4.0$ | $4.25$ | $5.0$ | $6.0$ |
|---|---|---|---|---|---|
| $10$ | $0.983$ ($6$) | $0.900$ ($6$) | $0.800$ ($7$) | $0.533$ ($9$) | $0.167$ ($9$) |
| $15$ | $1.000$ ($8$) | $0.867$ ($8$) | $0.800$ ($10$) | $0.350$ ($11$) | $0.100$ ($11$) |
| $20$ | $0.983$ ($9$) | $0.850$ ($12$) | $0.650$ ($14$) | $0.283$ ($17$) | $0.067$ ($15$) |
Observation 2.3 the cliff position differs greatly with the number of literals. 2-SAT collapses between $\alpha=1$ and $1.5$, and the cliff sharpens as variables increase. 3-SAT with $20$ variables gives $0.583$ at $\alpha=4.5$ and $0.283$ at $5.0$, collapsing beyond $4$: the $200$ 2-SAT problems solved with the implication graph and the $100$ 3-SAT problems solved by branching agreed with trying all assignments.
3. Work Near the Cliff
Computation 3.1: with the same branching solver, branches near the cliff ($\alpha=4.25$ for 3-SAT, $\alpha=1.0$ for 2-SAT) were counted on $40$ problems for each number of variables.
| formula | variables | branches (median, mean) |
|---|---|---|
| 3-SAT | $10$ | $7$, $6.700000$ |
| 3-SAT | $20$ | $13$, $14.575000$ |
| 3-SAT | $30$ | $23$, $26.500000$ |
| 3-SAT | $40$ | $47$, $49.225000$ |
| 2-SAT | $20$ | $6$, $6.100000$ |
| 2-SAT | $40$ | $9$, $9.375000$ |
| 2-SAT | $80$ | $16$, $15.875000$ |
| 2-SAT | $160$ | $30$, $27.875000$ |
Observation 3.2 this is the core. The work near the cliff grows differently. Doubling the variables from $20$ to $40$ multiplies the mean branches by $3.377358$ for 3-SAT and by $1.536885$ for 2-SAT: for 2-SAT each doubling gives $1.536885$, $1.693333$ and $1.755906$, and $8$ times the variables give $4.569672$ times the branches, slower than proportional. For 3-SAT, $4$ times the variables give $7.347015$ times, faster than proportional.
4. The Separator
Observation 4.1 the separator is whether one looks at the share satisfiable or at the branches needed to solve. Looking only at the share satisfiable, both 2-SAT and 3-SAT have a cliff: looking at branches, the work outgrows the variables on the cliff only with three literals. With two, settling one literal settles the rest in a chain, leaving few places to split.
Observation 4.2 placed beside Paper 348. 348 showed that on the same graph, connecting is cheap and ordering is not. There, two questions on the same graph split the work. Here, formulas of the same form split both the cliff position and the growth of work depending only on two or three literals per clause.
Observation 4.3 what is not said. The relation of P and NP, the cliff position as variables grow without bound, and comparisons of good solvers are not treated. What is shown is that two or three literals per clause changes both where the cliff lies and how the work near it grows.
5. Census and Closing
- clause ratio $\alpha=m/n$ (Section 1): the axis for the cliff.
- both solvers correct (Observation 2.3): $200$ and $100$ problems.
- 2-SAT at $\alpha=1.5$: $0.695$ to $0.025$ (Computation 2.1): the cliff sharpens.
- 2-SAT at $\alpha=1.0$: $0.945$ (Computation 2.1): $320$ variables.
- 3-SAT at $\alpha=5.0$: $0.283$ (Computation 2.2): the cliff further right.
- 3-SAT branches $\mathbf{3.377358}$-fold (Observation 3.2): the core.
- 2-SAT branches $\mathbf{1.536885}$-fold (Observation 3.2): doubled variables.
- 2-SAT: $4.569672$-fold for $8$ times (Observation 3.2): slower than proportional.
- 3-SAT: $7.347015$-fold for $4$ times (Observation 3.2): faster than proportional.
- share satisfiable, or branches (Observation 4.1): the separator; Paper 348.
Closing: Two or three literals per clause moves the cliff of satisfiability and changes how the work near it grows. 2-SAT collapses between $\alpha=1$ and $1.5$, falling at $\alpha=1.5$ from $0.695$ with $20$ variables to $0.025$ with $320$; 3-SAT collapses beyond $4$, because more literals give each clause more ways to be satisfied, so the same number of clauses collapses later. Doubling the variables from $20$ to $40$ with the same branching solver multiplies the mean branches near the cliff by $3.377358$ for 3-SAT and by $1.536885$ for 2-SAT: with two literals, settling one settles the rest in a chain; with three, places to split remain. Placed among the earlier papers: beside Paper 348’s “connecting is cheap and ordering is not”, we placed that only the number of literals per clause splits the work for formulas of the same form. To be honest: the formulas are small, and neither the limiting cliff position nor the work of good solvers is stated.
References
- Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
- Mézard, M., & Montanari, A. (2009). Information, Physics, and Computation. Oxford University Press.
- Yamagishi, Y. (2026). On the Same Graph, Connecting Is Cheap and Ordering Is Not [Paper 348]. YOI: https://www.yamagishiyuuki.com/yoi/348; DOI: 10.5281/zenodo.22683555
Reference
Yamagishi, Y. (2026). Two or Three Literals per Clause Moves the Cliff of Satisfiability and Changes How the Work Near It Grows [Paper 874]. YOI: https://www.yamagishiyuuki.com/yoi/874
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 874. This paper is a preprint and has not been peer reviewed.