目录

一文讲清楚:SAT

先说结论:作为一个「代码术语」,SAT 最主流的含义是 Boolean Satisfiability Problem —— 布尔可满足性问题:给定一个由布尔变量、与、或、非组成的公式,问「是否存在一组真假取值,让整个公式为真」。答「存在」叫 SAT(可满足),答「不存在」叫 UNSAT(不可满足)。它是计算机科学里第一个被证明的 NP 完全问题,也是今天形式验证、约束求解、依赖解析背后的实际引擎。

不过 SAT 是个高度依赖语境的缩写,判断方法和 exp、blk 一样:看它出现在哪一层。

页面末尾附有全文结构的思维导图。

1. 义项速览

语境 SAT 指什么 典型长相
算法 / 论文 / 验证工具 Boolean Satisfiability,布尔可满足性问题 SAT solver、UNSAT、p cnf、3-SAT
芯片 / EDA / 形式验证 同上,指用 SAT 求解做等价性检查、模型检查 SAT sweeping、BMC
程序验证 / 安全 常常其实是 SMT(SAT 加理论),口语里被简写成 SAT z3、cvc5、SMT-LIB
网络设备 / 防火墙 Address Translation,地址转换(静态 / 源地址) 配置里的 SAT,与 SNAT、DNAT 并列
工程交付 / 制造 Site Acceptance Test,现场验收测试 与 FAT(出厂验收)成对出现
考试 / 留学 Scholastic Assessment Test,美国大学入学考试 分数区间 400–1600
前端 / 图形 saturation,饱和度 saturate()、HSL 里的 S
文件后缀 .sat 是 ACIS 的三维实体模型格式 part.sat
一句话判据:**代码、论文、验证工具里的 ''sat'' 就是「可满足性」;只有当它出现在网络配置或验收文档里,才轮到「地址转换」「现场验收」。**

下面只展开第一条 —— 它才是开发者日常真正会撞上 SAT 的地方。

2. SAT 问题到底是什么

SAT 问题的输入是一个命题逻辑公式,输出只有一个 bit:可满足,还是不可满足。

先记住这五个零件,读论文、看代码、调求解器都要用:

术语 英文 说明 例子
变量 variable 只能取真 / 假 x1、x2
文字 literal 变量本身,或它的否定 x1、¬x3
子句 clause 若干文字的或 (x1 ∨ ¬x3)
合取范式 CNF 若干子句的与 见下
赋值 / 模型 assignment / model 给每个变量定值;让公式为真的赋值叫模型 x1=T, x2=F, x3=T

标准形式是 CNF(Conjunctive Normal Form,合取范式):

(x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1)

变量:x1 x2 x3
子句:(x1 ∨ ¬x3)        ← 2 个文字
      (x2 ∨ x3 ∨ ¬x1)   ← 3 个文字

代入赋值 x1=T, x2=F, x3=T:
  子句 1:T ∨ F     = T  ✔
  子句 2:F ∨ T ∨ F = T  ✔
→ 整个公式为真,这个实例是 SAT

为什么要标准化成 CNF:任何布尔公式都能在多项式时间内转成 CNF(用 Tseitin 变换,见第 3 节),所以「一般 SAT」与「CNF-SAT」难度等价,教科书里的定义就统一写 CNF 了。

再补两个周边概念:

3. 怎么把现实问题变成 CNF

SAT 之所以有用,是因为大量组合问题都能表述成「一组布尔约束同时成立」。常见三招。

3.1 有约束就直接写子句

3.2 任意公式 → Tseitin 变换

直接展开成 CNF 会指数膨胀(「或套与」这种形状尤其明显)。Tseitin 的做法是给每个子公式起一个辅助变量,用少量子句把它们钉在一起:

原始:(A ∧ B) ∨ (C ∧ D)
引入:t1 ↔ (A ∧ B)、t2 ↔ (C ∧ D),目标写成 t1 ∨ t2
结果:CNF 规模与公式大小成线性,代价是变量变多

工业界几乎所有编码都走这条路:用变量换结构。

3.3 「恰好一个」的编码别写笨了

两两互斥的写法在 n 个候选时会产生 C(n,2) 个子句,n 一上去就爆炸。替代方案:

编码 子句规模 特点
两两互斥(pairwise) O(n²) 最简单直白,n 小的时候照用
顺序编码(sequential / ladder) O(n) 引入辅助变量,通用性好
二进制 / 位向量编码 O(n log n) 候选本身是编号时最自然,但对单元传播不友好
commander 编码 O(n),常数更小 大规模 at-most-one 的常用选择

3.4 涉及整数、数组、字符串时,别硬转

「x + y ≤ 10」「下标 i 的元素等于 v」这类约束手工编码成布尔子句能写,但极其痛苦且容易出错。这种情况直接用 SMT(SAT Modulo Theories)—— 底层还是 SAT,只是外面套了算术、位向量、数组、字符串等理论求解器。

4. DIMACS CNF:SAT 世界的通用文本格式

SAT 工具的输入格式几乎都是 DIMACS CNF(.cnf 后缀),几行就能读完:

c 注释:(x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1)
p cnf 3 2
1 -3 0
2 3 -1 0

逐行解释:

命令行跑一下:

cadical example.cnf
# s SATISFIABLE
# v 1 -2 3 0
 
minisat example.cnf out.txt      # 结果写进 out.txt

用 Python 直接调(PySAT 把主流求解器封装成统一接口):

from pysat.formula import CNF
from pysat.solvers import Glucose3
 
cnf = CNF(from_clauses=[[1, -3], [2, 3, -1]])
with Glucose3(bootstrap_with=cnf) as g:
    print(g.solve())        # True
    print(g.get_model())    # [1, -2, 3]
 
# 也可以直接读 DIMACS 文件:
# cnf = CNF(from_file="example.cnf")

需要「不只是布尔」时用 Z3:

from z3 import Int, Solver, sat
 
x, y = Int("x"), Int("y")
s = Solver()
s.add(x + y <= 10, x > 3, y >= 0)
print(s.check())            # sat / unsat / unknown
print(s.model())

5. 复杂度:从线性可解到大名鼎鼎的 NP 完全

同样是「布尔公式可满足吗」,限制不同,难度天差地别:

问题 形状限制 复杂度 说明
2-SAT 每条子句至多 2 个文字 线性时间 建蕴含图求强连通分量(SCC)即可
Horn-SAT 每条子句至多 1 个正文字 线性时间 单元传播跑到底,不需要回溯
3-SAT 每条子句恰好 3 个文字 NP 完全 Karp 1972,SAT 最经典的特例
CNF-SAT 一般形式 NP 完全 Cook–Levin 定理(1971),第一个被证明的 NP 完全问题
#SAT 数有多少个解 #P 完全 比判定更难,模型计数用
MaxSAT 最多能同时满足多少子句 NP 难(优化版) 配置修复、软约束场景常用
QBF 公式里带 ∀ / ∃ 量词 PSPACE 完全 表达能力更强

2-SAT 的经典做法值得单独记一下:

子句 (¬a ∨ b) 等价于蕴含 (a → b)
对每条子句补出两条蕴含边,建成有向图
若某个变量 x 与 ¬x 落在同一个强连通分量里 → UNSAT
否则按 SCC 逆拓扑序取值即可得到解
注意:**「NP 完全」说的是最坏情况**。它意味着没有已知的多项式时间算法(且普遍认为不存在),但**不意味着实际算不动** —— 见第 7 节。

6. 求解器怎么解:DPLL 与 CDCL

现代 SAT 求解器绝大多数属于 CDCL 系。理解它,先懂它的前身 DPLL。

6.1 DPLL:单元传播 + 回溯

简化流程:
  ① 单元传播:某子句只剩一个未赋值文字时,它就必须为真 → 立刻赋值
                 若产生空子句(冲突)→ 回退
  ② 分支:挑一个未赋值的变量,先试 true
  ③ 回溯:走不通就换 false;全部穷尽仍然冲突 → UNSAT

思路朴素,但光是单元传播这一步,就已经能砍掉绝大部分搜索空间。

6.2 CDCL:让求解器「从冲突中学习」

CDCL(Conflict-Driven Clause Learning)在 DPLL 上加了四件关键的事:

再叠上周期性重启(Luby / 几何序列)和子句删除(防止子句库无限膨胀),就是今天工业级求解器的骨架。

术语时间线,看到别陌生:

名字 年份 贡献
DP / DPLL 1960 / 1962 单元传播 + 回溯的基础框架
GRASP 1996 冲突分析与学习子句
Chaff 2001 VSIDS + 两文字监视,速度飞跃
MiniSat 2003 极简开源实现,成为后来几乎所有求解器的起点
现代求解器 2010s– 预处理、inprocessing、更聪明的重启与启发

6.3 求解器的输出有三种

6.4 主流工具

工具 类型 适用场景
MiniSat / Glucose / CaDiCaL / Kissat 纯 SAT 工业与竞赛标准件,CaDiCaL、Kissat 常年在 SAT Competition 前列
CryptoMiniSat 纯 SAT 对 XOR 约束专门优化,密码学实例常用
PySAT Python 封装 一行代码切换求解器,适合实验与教学
Z3 / CVC5 / Yices SMT 支持整数、实数、位向量、数组、字符串等理论
商用求解器 SMT / 优化 带支持服务,强调工程集成与规模

7. 理论那么难,工程上真的解得动吗

解得动,而且常被低估。原因是最坏情况和实际实例是两回事:

一句话:SAT 的难度不在规模,在结构。

8. SAT 用在哪里

领域 在做什么 为什么落到 SAT
硬件形式验证 等价性检查、模型检查、BMC 「两个电路在任意输入下输出相同」本身就是布尔公式
软件验证 限界模型检查、符号执行、测试生成 把路径条件编成 CNF,有解即存在触发该路径的输入
SMT / 程序验证 合约检查、类型推断、漏洞检测 在 SAT 之上加算术等理论(z3、cvc5)
自动规划 SATPLAN 一类规划器 把「第 t 步执行什么动作」编成变量,约束编成子句
依赖解析 包管理器选版本 版本约束本质是布尔组合问题(见下)
配置与排产 特性开关、装箱、排课、调度 大量互斥 / 蕴含约束,天然是 CNF
EDA 布局布线、时序与功耗约束 布尔约束 + 优化目标(MaxSAT)
谜题与游戏 数独、N 皇后、扫雷、图着色 经典教学案例:把规则写成子句即可
密码分析 对简化轮数密码搜原像 / 碰撞 密码本身可展开成布尔电路,求解器即搜索器
模型计数 #SAT / 概率推断 数解的个数,属 #P 难度
配置修复 MaxSAT 找「改动最小且满足全部硬约束」的方案

包管理器那条多解释一句:「装 A 需要 B ≥ 2 且 C < 3,而 B ≥ 2 恰与 C < 3 互斥」 —— 这就是一个布尔约束求解问题。Dart 的 pub、Cargo 新版 resolver 用的 PubGrub 都属于 CDCL 风格求解;所以你在包管理器报错里看到的「回溯、冲突、无法找到兼容版本」,和 SAT 求解器的日志是同一套思路。

9. 别和这些缩写混淆

缩写 全称 一句话区分
SAT Boolean Satisfiability 布尔公式有没有解(本页主角)
SMT Satisfiability Modulo Theories SAT 加理论:算术、位向量、数组、字符串
SAST / DAST Static / Dynamic Application Security Testing 源码扫描 / 运行时扫描,与可满足性无关
3-SAT 3-CNF SAT SAT 的特例,子句恰好 3 个文字,仍是 NP 完全
SNAT / DNAT / SAT (Source / Destination) Address Translation 网络地址转换,出现在防火墙配置而非代码里
.sat ACIS 实体模型文件 三维建模格式,与求解器无关
saturate() 饱和度调整 CSS 滤镜 / HSL 色彩模型里的 S

另外还有两个纯生活语境,撞见了别多想:

10. 常见坑

现象 原因 处理方向
求解器返回 UNKNOWN 就当无解 UNKNOWN 只是「没在预算内算完」 放宽时限、调参数、换求解器;别把三态压成两态
拿纯 SAT 求解器去解明显是整数规划的问题 硬把整数编码成布尔,变量爆炸 直接上 SMT 或专用求解器
CNF 文件头数字与内容不符 p cnf n m 改了一半 由生成器统一维护,不要手改
编码完变量一大就解不动 「恰好一个」用了 O(n²) 两两互斥 换顺序 / commander 编码
UNSAT 结果无法复核 没保留证明 让求解器输出 DRAT,用校验器独立验证
随机实例解不动,就断言「SAT 不行」 随机 3-SAT 本身就是最难的一类 换建模方式,减少对称性
换个求解器后模型不同 求解顺序受启发式影响 把 SAT / UNSAT 当结论,模型按需解读
把 SAT 与 SMT 混着说 口语化简写 明确写「布尔 SAT」还是「SMT」

倒数第二条展开一句:同一个公式,不同求解器、不同版本给出的模型可能完全不同,但 SAT / UNSAT 的结论必须一致。 若结论不一致,那是求解器或编码的 bug,不是「口味问题」。

11. 一句话总结

SAT 就是问「**存不存在一组真假取值,让这个布尔公式为真**」:答「存在」给一个赋值(模型),答「不存在」给一份可校验的证明。它是历史上第一个被证明的 **NP 完全**问题(Cook–Levin 1971),却是工程上最成功的「难问题」之一 —— CDCL 求解器能从冲突中学习,把电路、程序、依赖关系这类**有结构**的问题解到百万变量规模。看到代码或工具里的 ''sat'' / ''SAT'' / ''UNSAT'',基本都在说这件事。

相关:exp · blk · hex · buffer


返回:代码术语

# SAT
## 判断语境
- 算法 / 论文 / 验证工具 → 可满足性问题
- 网络配置 → 地址转换
- 工程交付 → 现场验收测试
- 考试 / 留学 → 美国高考
- 前端色彩 → saturation 饱和度
## SAT 问题是什么
### 五个零件
- 变量 x1 x2 x3:只有真 / 假
- 文字:x 或 ¬x
- 子句:若干文字的或
- CNF:若干子句的与
- 赋值 / 模型:让公式为真的取值
### 结论只有两种
- SAT:存在满足的赋值
- UNSAT:任何赋值都不满足
### 例子
- (x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1)
- x1=T, x2=F, x3=T 即满足
## 怎么编码成 CNF
### 约束直接写
- 互斥:¬A ∨ ¬B
- 蕴含:¬A ∨ B
- 恰好一个:至少一个 + 两两互斥
### Tseitin 变换
- 给子公式起辅助变量
- 规模从指数降到线性
- 代价是变量变多
### at-most-one 编码
- pairwise:O(n²),n 小才用
- sequential:O(n)
- 二进制:O(n log n)
- commander:常数更小
### 有整数就上 SMT
- 算术、数组、字符串别硬编
## DIMACS CNF
- c 开头是注释
- p cnf 变量数 子句数
- 每行一个子句,以 0 结尾
- 正数原文,负数取反
- cadical / minisat 直接吃这个格式
- PySAT:Glucose3 + add_clause
## 复杂度
- 2-SAT:线性,蕴含图 SCC
- Horn-SAT:线性,单元传播
- 3-SAT:NP 完全(Karp 1972)
- CNF-SAT:NP 完全(Cook–Levin 1971)
- #SAT:数解的个数,#P 完全
- MaxSAT:最大满足,NP 难
- QBF:带量词,PSPACE 完全
## 求解器原理
- DPLL:单元传播 + 分支回溯
- CDCL:冲突驱动子句学习
- 学习子句永久有效
- 非时序回溯,一步跳很远
- VSIDS 分支启发
- 两文字监视加速传播
- Luby 重启、子句删除
- 输出三态:SAT / UNSAT / UNKNOWN
- UNSAT 带 DRAT 证明可校验
## 工具
- MiniSat、Glucose、CaDiCaL、Kissat
- CryptoMiniSat:XOR 友好
- PySAT:Python 统一接口
- Z3 / CVC5 / Yices:SMT
## 工程现实
- 百万变量、千万子句的实例可解
- 难在结构,不在规模
- 随机 3-SAT 才是真硬
- 预处理先缩小问题
## 用在哪
- 硬件形式验证、等价性检查
- 限界模型检查 BMC
- 符号执行、测试生成
- SMT 与程序验证
- 自动规划 SATPLAN
- 依赖解析:PubGrub 风格
- 配置、装箱、排课、调度
- 数独、N 皇后、图着色
- 密码分析搜原像
- MaxSAT 最小改动修复
## 别混淆
- SMT = SAT + 理论
- SAST / DAST:源码与应用扫描
- 3-SAT 是 SAT 的特例
- SNAT / DNAT:网络地址转换
- SAT 考试、Site Acceptance Test
- .sat:ACIS 三维模型
- saturate():饱和度
## 常见坑
- UNKNOWN 当成无解
- 整数问题硬编码成布尔
- p cnf 头信息与内容不符
- at-most-one 写成 O(n²)
- UNSAT 不留证明
- 拿随机实例判定 SAT 不行
- 以为模型不同是结论不同
## 记住这句
- SAT 问「有没有一组取值让公式成立」
- 它是第一个被证明的 NP 完全问题
- CDCL 让有结构的工业实例真的可解