关于「规则叠加的悬崖:随机 3-SAT 的可满足性相变」,《规则叠加的悬崖》给出的定量结论是什么?
结论:第一章正面陈述并量化命题,并修正立项蓝图:4.26 出自 2002 年空腔方法的 4.267,而非蓝图所引的 1992 年实验(约 4.3)或 1994 年外推(约 4.17),且至今只严格证明了 3.52 与 4.4898 两个界;开关数 50 时一半位置在 4.33。
数据口径:书中规则册与数据均为示意;全部计算由书中程序生成;本书属非个人化经营方法,不构成法律、合规或经营决策意见。 第四章给一本 24 个开关的示意规则册做体检:裸约束比 0.958,载荷 0.475,死锁时约束比中位数只有 1.292,最小冲突核横跨三个规则族。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
查看完整验算程序
# 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])))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布尔可满足性相变阈值、促销合规与门禁叠加的约束比临界与全盘死锁预警母典》第 1 章「规则叠加的悬崖:随机 3-SAT 的可满足性相变」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}