显示页面讨论过去修订反向链接回到顶部 本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。 ====== 一文讲清楚:SAT ====== 先说结论:**作为一个「代码术语」,''SAT'' 最主流的含义是 Boolean Satisfiability Problem —— 布尔可满足性问题**:给定一个由布尔变量、与、或、非组成的公式,问「**是否存在一组真假取值,让整个公式为真**」。答「存在」叫 **SAT(可满足)**,答「不存在」叫 **UNSAT(不可满足)**。它是计算机科学里**第一个被证明的 NP 完全问题**,也是今天形式验证、约束求解、依赖解析背后的实际引擎。 不过 ''SAT'' 是个高度依赖语境的缩写,判断方法和 [[代码术语:exp|exp]]、[[代码术语:blk|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,合取范式): <code> (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 </code> 为什么要标准化成 CNF:**任何**布尔公式都能在多项式时间内转成 CNF(用 Tseitin 变换,见第 3 节),所以「一般 SAT」与「CNF-SAT」难度等价,教科书里的定义就统一写 CNF 了。 再补两个周边概念: * **UNSAT**:不存在任何能满足的赋值。它不是一个「没算出来」的中间状态,而是一个**结论** —— 而且是可以被独立证明的结论(见第 6 节)。 * **判定 vs 求解**:''SAT'' 这个名字问的是「有没有解」(判定问题);但多数场景还需要把那个解拿出来用,所以求解器在报 ''s SATISFIABLE'' 之后,通常会给一行 ''v ...'' 的模型。 ===== 3. 怎么把现实问题变成 CNF ===== SAT 之所以有用,是因为大量组合问题都能表述成「一组布尔约束同时成立」。常见三招。 ==== 3.1 有约束就直接写子句 ==== * 「A 与 B 不能同时为真」→ ''(¬A ∨ ¬B)'' * 「A 蕴含 B」→ ''(¬A ∨ B)'' * 「至少选一个」→ ''(A ∨ B ∨ C)'' * 「恰好选一个」→ 至少一个,加两两互斥:''(A ∨ B ∨ C) ∧ (¬A ∨ ¬B) ∧ (¬A ∨ ¬C) ∧ (¬B ∨ ¬C)'' ==== 3.2 任意公式 → Tseitin 变换 ==== 直接展开成 CNF 会指数膨胀(「或套与」这种形状尤其明显)。Tseitin 的做法是**给每个子公式起一个辅助变量**,用少量子句把它们钉在一起: <code> 原始:(A ∧ B) ∨ (C ∧ D) 引入:t1 ↔ (A ∧ B)、t2 ↔ (C ∧ D),目标写成 t1 ∨ t2 结果:CNF 规模与公式大小成线性,代价是变量变多 </code> 工业界几乎所有编码都走这条路:**用变量换结构**。 ==== 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'' 后缀),几行就能读完: <code> c 注释:(x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1) p cnf 3 2 1 -3 0 2 3 -1 0 </code> 逐行解释: * ''c'' 开头是注释行 * ''p cnf <变量数> <子句数>'' 是头信息,**这两个数字必须和实际内容一致**,多数求解器靠它预分配内存 * 每个子句写一行,用 **0 结尾**;正数表示变量本身,负数表示取反,变量编号从 1 开始 * 上面第二行数据 ''1 -3 0'' 就是 ''(x1 ∨ ¬x3)'' 命令行跑一下: <code bash> cadical example.cnf # s SATISFIABLE # v 1 -2 3 0 minisat example.cnf out.txt # 结果写进 out.txt </code> 用 Python 直接调(PySAT 把主流求解器封装成统一接口): <code python> 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") </code> 需要「不只是布尔」时用 Z3: <code python> 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()) </code> ===== 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 的经典做法值得单独记一下: <code> 子句 (¬a ∨ b) 等价于蕴含 (a → b) 对每条子句补出两条蕴含边,建成有向图 若某个变量 x 与 ¬x 落在同一个强连通分量里 → UNSAT 否则按 SCC 逆拓扑序取值即可得到解 </code> > 注意:**「NP 完全」说的是最坏情况**。它意味着没有已知的多项式时间算法(且普遍认为不存在),但**不意味着实际算不动** —— 见第 7 节。 ===== 6. 求解器怎么解:DPLL 与 CDCL ===== 现代 SAT 求解器绝大多数属于 **CDCL** 系。理解它,先懂它的前身 **DPLL**。 ==== 6.1 DPLL:单元传播 + 回溯 ==== <code> 简化流程: ① 单元传播:某子句只剩一个未赋值文字时,它就必须为真 → 立刻赋值 若产生空子句(冲突)→ 回退 ② 分支:挑一个未赋值的变量,先试 true ③ 回溯:走不通就换 false;全部穷尽仍然冲突 → UNSAT </code> 思路朴素,但光是**单元传播**这一步,就已经能砍掉绝大部分搜索空间。 ==== 6.2 CDCL:让求解器「从冲突中学习」 ==== CDCL(Conflict-Driven Clause Learning)在 DPLL 上加了四件关键的事: * **冲突分析 + 学习子句**:每次冲突都分析出「究竟是哪几个赋值凑成了必然矛盾」,把它写成一个**新子句**加进公式。这条子句永久有效,后面不会再踩同一个坑 * **非时序回溯**:不是退一步,而是**直接跳回**真正导致冲突的那一层,一步跨很远 * **分支启发**:用 VSIDS 之类的策略,优先选「最近频繁出现在冲突里」的变量 * **两文字监视**(watched literals):每个子句只盯两个文字,单元传播时只需检查少量子句,速度提升巨大 再叠上**周期性重启**(Luby / 几何序列)和**子句删除**(防止子句库无限膨胀),就是今天工业级求解器的骨架。 术语时间线,看到别陌生: ^ 名字 ^ 年份 ^ 贡献 ^ | DP / DPLL | 1960 / 1962 | 单元传播 + 回溯的基础框架 | | GRASP | 1996 | 冲突分析与学习子句 | | Chaff | 2001 | VSIDS + 两文字监视,速度飞跃 | | MiniSat | 2003 | 极简开源实现,成为后来几乎所有求解器的起点 | | 现代求解器 | 2010s– | 预处理、inprocessing、更聪明的重启与启发 | ==== 6.3 求解器的输出有三种 ==== * ''SATISFIABLE'' + 模型 ''v ...'':找到解 * ''UNSATISFIABLE'':无解,**通常还附带一份可独立校验的证明**(DRAT / DRUP 格式),第三方校验器能复核 —— 这是形式验证敢把安全性押在 SAT 上的底气 * ''UNKNOWN'':超时或触到资源上限。**这不等于无解** ==== 6.4 主流工具 ==== ^ 工具 ^ 类型 ^ 适用场景 ^ | MiniSat / Glucose / CaDiCaL / Kissat | 纯 SAT | 工业与竞赛标准件,CaDiCaL、Kissat 常年在 SAT Competition 前列 | | CryptoMiniSat | 纯 SAT | 对 XOR 约束专门优化,密码学实例常用 | | PySAT | Python 封装 | 一行代码切换求解器,适合实验与教学 | | Z3 / CVC5 / Yices | SMT | 支持整数、实数、位向量、数组、字符串等理论 | | 商用求解器 | SMT / 优化 | 带支持服务,强调工程集成与规模 | ===== 7. 理论那么难,工程上真的解得动吗 ===== 解得动,而且常被低估。原因是**最坏情况**和**实际实例**是两回事: * 工业实例大多来自电路、程序、配置这类**有结构**的问题,CDCL 学习出的子句正好抓住这些结构 * 现代求解器能处理**百万级变量、千万级子句**的实例;SAT Competition 的工业组就是拿真实 EDA / 验证问题当题面 * 求解前还有成体系的**预处理**(变量消除、子句化简、等价变量合并),先把问题缩小再动手 * 反过来说:**无结构的随机 3-SAT 依然很难**,接近相变阈值的地方尤其硬 —— 这才是「SAT 太慢」的真实来源 一句话:**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 | 另外还有两个纯生活语境,撞见了别多想: * **SAT** = Scholastic Assessment Test,美国大学入学考试(总分 400–1600) * **SAT** = Site Acceptance Test,工程交付里的**现场验收测试**,与 FAT(Factory Acceptance Test,出厂验收)配对 ===== 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|exp]] · [[代码术语:blk|blk]] · [[代码术语:hex|hex]] · [[代码术语:buffer|buffer]] ---- 返回:[[代码术语]] ```mdk height=600 color=#7c3aed # 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 让有结构的工业实例真的可解 ``` 登录 Detach Close 该主题尚不存在 您访问的页面并不存在。如果允许,您可以使用创建该页面按钮来创建它。 代码术语/sat.txt 最后更改: 2026/10/16 12:32由 张叶安 登录