What does The Cliff of Stacked Rules conclude, in numbers, about “The Cliff of Stacked Rules: the Satisfiability Phase Transition of Random 3-SAT”?
Answer: Chapter 1 states and quantifies the claim and corrects the blueprint: 4.26 comes from the cavity-method value of 4.267 of 2002, not from the 1992 experiments (about 4.3) or the 1994 extrapolation (about 4.17) that the blueprint cites, and only the bounds 3.52 and 4.4898 have been proved; with 50 switches the half-way point is 4.33.
Scope of the numbers: The rulebooks and data are illustrative; every calculation is generated by the book's programs; the book offers general business method, not legal, compliance or business-decision advice. Chapter 4 checks an illustrative rulebook of 24 switches: bare ratio 0.958, load 0.475, a median clause ratio at deadlock of only 1.292, and a minimal conflict core spanning three rule families.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 4.33, 50
| random 3-SAT, 100 formulas per point, seed 20261113 | ||
| alpha=m/n | P(sat) n=20 | P(sat) n=50 |
| 3.0 | 1.000 | 1.000 |
| 3.4 | 1.000 | 1.000 |
| 3.8 | 0.940 | 0.990 |
| 4.0 | 0.880 | 0.850 |
| 4.2 | 0.760 | 0.630 |
| 4.4 | 0.680 | 0.430 |
| 4.6 | 0.450 | 0.260 |
| 4.8 | 0.510 | 0.130 |
| 5.2 | 0.180 | 0.010 |
| 5.6 | 0.090 | 0.000 |
| 6.0 | 0.020 | 0.000 |
| n=20: 50 per cent point at alpha = 4.56 | ||
| n=50: 50 per cent point at alpha = 4.33 |
Show the full program
# Chapter 1. p11: share of random 3-SAT rule sets still satisfiable
# Model: random 3-SAT (Mitchell, Selman and Levesque 1992). n Boolean
# switches; m rules, each an OR of 3 distinct switches with random
# signs. alpha = m / n. A standard-library DPLL solver (unit
# propagation and branching) decides each formula. Sizes n = 20 and
# n = 50 and 100 formulas per point are illustrative small sizes;
# fixed seed. The 50 per cent point is read off by linear
# interpolation between grid points. Published large-n estimates of
# the 50 per cent point: about 4.3 (Mitchell et al. 1992), 4.17 from
# finite-size scaling (Kirkpatrick and Selman 1994), 4.267 from the
# cavity method, with clustering from 3.921 (Mezard, Parisi and
# Zecchina 2002); proven bounds 3.52 and 4.4898. The blueprint's
# 4.26 is the cavity value cut to two decimals.
import random
from collections import Counter
SEED = 20261113
TRIALS = 100
ALPHAS = [3.0, 3.4, 3.8, 4.0, 4.2, 4.4, 4.6, 4.8, 5.2, 5.6, 6.0]
def assign(cls, lit):
out = []
for c in cls:
if lit in c:
continue
if -lit in c:
c = [x for x in c if x != -lit]
if not c:
return None
out.append(c)
return out
def dpll(cls):
while True:
unit = next((c[0] for c in cls if len(c) == 1), None)
if unit is None:
break
cls = assign(cls, unit)
if cls is None:
return False
if not cls:
return True
w = Counter()
for c in cls:
for x in c:
w[x] += 1 << max(0, 6 - len(c))
lit = max(w, key=lambda x: (w[x] + w[-x], w[x], -abs(x), x))
for b in (lit, -lit):
nxt = assign(cls, b)
if nxt is not None and dpll(nxt):
return True
return False
def formula(rng, n, m):
out = []
for _ in range(m):
vs = rng.sample(range(1, n + 1), 3)
out.append([v if rng.random() < 0.5 else -v for v in vs])
return out
def crossing(alphas, ps):
for i in range(len(ps) - 1):
if ps[i] >= 0.5 > ps[i + 1]:
t = (ps[i] - 0.5) / (ps[i] - ps[i + 1])
return alphas[i] + t * (alphas[i + 1] - alphas[i])
return float("nan")
rng = random.Random(20261113)
table = {}
for n in (20, 50):
row = []
for a in ALPHAS:
m = round(a * n)
ok = 0
for _ in range(TRIALS):
if dpll(formula(rng, n, m)):
ok += 1
row.append(ok / TRIALS)
table[n] = row
print("random 3-SAT, %d formulas per point, seed %d" % (TRIALS, SEED))
print("alpha=m/n P(sat) n=20 P(sat) n=50")
for i, a in enumerate(ALPHAS):
print(" %4.1f %5.3f %5.3f"
% (a, table[20][i], table[50][i]))
for n in (20, 50):
print("n=%d: 50 per cent point at alpha = %.2f"
% (n, crossing(ALPHAS, table[n])))Single source and citation
Fan, Y. (2026). Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming (Version 1.0.0), Chapter 1: The Cliff of Stacked Rules: the Satisfiability Phase Transition of Random 3-SAT. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-252 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026252,
author = {Fan, Yafu},
title = {Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 2 · DPLL with the Standard Library: Unit Propagation, Branching and "Easy, Hard, Easy"
- Chapter 3 · Where the Cliff Lies: the First-Moment Bound, the Exact Threshold of 2-SAT and Rule Length
- Chapter 4 · Measuring a Rulebook: Load, Forced Values, Minimal Conflict Cores and Headroom
- Chapter 5 · Real Rules Are Not Random Rules: Mixed Lengths, the 2+p Model and the Balance of Demands and Prohibitions
- Chapter 6 · Signals on the Eve of Deadlock: Solution Counts, the Backbone and the Hazard of the Next Rule
- Chapter 7 · Classical Sources East and West: the Spear and Shield of the Han Feizi, and Boole's x² = x
- Chapter 8 · Closing the Loop: a Monthly Constraint-Ratio Scan of the Five-Kit Rulebooks and a Pre-Registered Test