What does The Cliff of Stacked Rules conclude, in numbers, about “DPLL with the Standard Library: Unit Propagation, Branching and "Easy, Hard, Easy"”?
Answer: DPLL decides whether a rulebook has a solution by simplification, unit propagation and branching with backtracking, and the steps of unit propagation are themselves a readable account of a deadlock. p21 shows a rulebook of only eight switches whose ratio after one new rule in week 2 is just 1.375, yet seven steps of unit propagation prove deadlock, because single-switch hard requirements pin the other rules down. p22 reproduces "easy, hard, easy": the median number of dead ends climbs from 0.0 to 26.5 and falls back to 9.0. p23 shows that unit propagation cuts the work by two orders of magnitude. But where exactly is the cliff, and can a bound be computed without experiments? The next chapter answers with the expected number of solutions, the exact threshold of 2-SAT and the length of clauses.
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: 0.0, 26.5, 9.0
| n = 50, 60 formulas per ratio; medians and 90th percentiles | |||||
| alpha | P(sat) | guesses | dead ends | dead ends p90 | max |
| 2.0 | 1.000 | 24.0 | 0.0 | 0.0 | 0 |
| 3.0 | 1.000 | 18.0 | 0.0 | 1.0 | 4 |
| 3.6 | 1.000 | 16.0 | 1.0 | 9.9 | 48 |
| 4.0 | 0.833 | 18.5 | 5.5 | 38.5 | 56 |
| 4.3 | 0.600 | 22.5 | 16.0 | 46.9 | 64 |
| 4.6 | 0.300 | 27.0 | 26.5 | 44.6 | 63 |
| 5.0 | 0.017 | 25.0 | 26.0 | 38.9 | 44 |
| 6.0 | 0.000 | 16.0 | 17.0 | 25.0 | 30 |
| 8.0 | 0.000 | 9.5 | 10.5 | 14.0 | 19 |
| 10.0 | 0.000 | 8.0 | 9.0 | 11.9 | 15 |
Show the full program
# Chapter 2. p22: easy-hard-easy - search effort peaks at the cliff
# Model: random 3-SAT on n = 50 switches, 60 formulas per ratio
# (illustrative), DPLL with unit propagation and a weighted branching
# rule. Effort = number of guesses (branch points) the solver opens.
# Under-constrained sets are solved almost without guessing, heavily
# over-constrained sets are refuted quickly, and the median effort
# peaks near the 50 per cent point (Mitchell et al. 1992).
import random
import statistics
from collections import Counter
N, TRIALS = 50, 60
ALPHAS = [2.0, 3.0, 3.6, 4.0, 4.3, 4.6, 5.0, 6.0, 8.0, 10.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, st):
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:
st[1] += 1
return False
if not cls:
return True
st[0] += 1
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 None:
st[1] += 1
elif dpll(nxt, st):
return True
return False
rng = random.Random(20261115)
print("n = %d, %d formulas per ratio; medians and 90th percentiles"
% (N, TRIALS))
print("alpha P(sat) guesses dead ends dead ends p90 max")
for a in ALPHAS:
m = round(a * N)
efforts, dead, ok = [], [], 0
for _ in range(TRIALS):
f = []
for _ in range(m):
vs = rng.sample(range(1, N + 1), 3)
f.append([v if rng.random() < 0.5 else -v for v in vs])
st = [0, 0]
if dpll(f, st):
ok += 1
efforts.append(st[0])
dead.append(st[1])
q = statistics.quantiles(dead, n=10)
print("%5.1f %6.3f %7.1f %9.1f %13.1f %4d"
% (a, ok / TRIALS, statistics.median(efforts),
statistics.median(dead), q[-1], max(dead)))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 2: DPLL with the Standard Library: Unit Propagation, Branching and "Easy, Hard, Easy". 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 1 · The Cliff of Stacked Rules: the Satisfiability Phase Transition of Random 3-SAT
- 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