差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
| 代码术语:sat [2026/10/16 12:29] – 创建 张叶安 | 代码术语:sat [2026/10/16 12:32] (当前版本) – 为 SAT 词条添加全文结构思维导图 张叶安 | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | 1 | + | ====== 一文讲清楚:SAT ====== |
| + | |||
| + | 先说结论:**作为一个「代码术语」,'' | ||
| + | |||
| + | 不过 '' | ||
| + | |||
| + | 页面末尾附有全文结构的思维导图。 | ||
| + | |||
| + | ===== 1. 义项速览 ===== | ||
| + | |||
| + | ^ 语境 ^ SAT 指什么 ^ 典型长相 ^ | ||
| + | | 算法 / 论文 / 验证工具 | Boolean Satisfiability,布尔可满足性问题 | '' | ||
| + | | 芯片 / EDA / 形式验证 | 同上,指用 SAT 求解做等价性检查、模型检查 | '' | ||
| + | | 程序验证 / 安全 | 常常其实是 SMT(SAT 加理论),口语里被简写成 SAT | '' | ||
| + | | 网络设备 / 防火墙 | Address Translation,地址转换(静态 / 源地址) | 配置里的 '' | ||
| + | | 工程交付 / 制造 | Site Acceptance Test,现场验收测试 | 与 '' | ||
| + | | 考试 / 留学 | Scholastic Assessment Test,美国大学入学考试 | 分数区间 400–1600 | | ||
| + | | 前端 / 图形 | saturation,饱和度 | '' | ||
| + | | 文件后缀 | '' | ||
| + | |||
| + | > 一句话判据:**代码、论文、验证工具里的 '' | ||
| + | |||
| + | 下面只展开第一条 —— 它才是开发者日常真正会撞上 '' | ||
| + | |||
| + | ===== 2. SAT 问题到底是什么 ===== | ||
| + | |||
| + | SAT 问题的输入是一个**命题逻辑公式**,输出只有一个 bit:**可满足,还是不可满足**。 | ||
| + | |||
| + | 先记住这五个零件,读论文、看代码、调求解器都要用: | ||
| + | |||
| + | ^ 术语 ^ 英文 ^ 说明 ^ 例子 ^ | ||
| + | | 变量 | variable | 只能取真 / 假 | '' | ||
| + | | 文字 | literal | 变量本身,或它的否定 | '' | ||
| + | | 子句 | clause | 若干文字的**或** | '' | ||
| + | | 合取范式 | CNF | 若干子句的**与** | 见下 | | ||
| + | | 赋值 / 模型 | assignment / model | 给每个变量定值;让公式为真的赋值叫模型 | '' | ||
| + | |||
| + | 标准形式是 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 了。 | ||
| + | |||
| + | 再补两个周边概念: | ||
| + | |||
| + | * **UNSAT**:不存在任何能满足的赋值。它不是一个「没算出来」的中间状态,而是一个**结论** —— 而且是可以被独立证明的结论(见第 6 节)。 | ||
| + | * **判定 vs 求解**:'' | ||
| + | |||
| + | ===== 3. 怎么把现实问题变成 CNF ===== | ||
| + | |||
| + | SAT 之所以有用,是因为大量组合问题都能表述成「一组布尔约束同时成立」。常见三招。 | ||
| + | |||
| + | ==== 3.1 有约束就直接写子句 ==== | ||
| + | |||
| + | * 「A 与 B 不能同时为真」→ '' | ||
| + | * 「A 蕴含 B」→ '' | ||
| + | * 「至少选一个」→ '' | ||
| + | * 「恰好选一个」→ 至少一个,加两两互斥:'' | ||
| + | |||
| + | ==== 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**('' | ||
| + | |||
| + | < | ||
| + | c 注释:(x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1) | ||
| + | p cnf 3 2 | ||
| + | 1 -3 0 | ||
| + | 2 3 -1 0 | ||
| + | </ | ||
| + | |||
| + | 逐行解释: | ||
| + | |||
| + | * '' | ||
| + | * '' | ||
| + | * 每个子句写一行,用 **0 结尾**;正数表示变量本身,负数表示取反,变量编号从 1 开始 | ||
| + | * 上面第二行数据 '' | ||
| + | |||
| + | 命令行跑一下: | ||
| + | |||
| + | <code bash> | ||
| + | cadical example.cnf | ||
| + | # s SATISFIABLE | ||
| + | # v 1 -2 3 0 | ||
| + | |||
| + | minisat example.cnf out.txt | ||
| + | </ | ||
| + | |||
| + | 用 Python 直接调(PySAT 把主流求解器封装成统一接口): | ||
| + | |||
| + | <code python> | ||
| + | from pysat.formula import CNF | ||
| + | from pysat.solvers import Glucose3 | ||
| + | |||
| + | cnf = CNF(from_clauses=[[1, | ||
| + | with Glucose3(bootstrap_with=cnf) as g: | ||
| + | print(g.solve()) | ||
| + | print(g.get_model()) | ||
| + | |||
| + | # 也可以直接读 DIMACS 文件: | ||
| + | # cnf = CNF(from_file=" | ||
| + | </ | ||
| + | |||
| + | 需要「不只是布尔」时用 Z3: | ||
| + | |||
| + | <code python> | ||
| + | from z3 import Int, Solver, sat | ||
| + | |||
| + | x, y = Int(" | ||
| + | s = Solver() | ||
| + | s.add(x + y <= 10, x > 3, y >= 0) | ||
| + | print(s.check()) | ||
| + | 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 上加了四件关键的事: | ||
| + | |||
| + | * **冲突分析 + 学习子句**:每次冲突都分析出「究竟是哪几个赋值凑成了必然矛盾」,把它写成一个**新子句**加进公式。这条子句永久有效,后面不会再踩同一个坑 | ||
| + | * **非时序回溯**:不是退一步,而是**直接跳回**真正导致冲突的那一层,一步跨很远 | ||
| + | * **分支启发**:用 VSIDS 之类的策略,优先选「最近频繁出现在冲突里」的变量 | ||
| + | * **两文字监视**(watched literals):每个子句只盯两个文字,单元传播时只需检查少量子句,速度提升巨大 | ||
| + | |||
| + | 再叠上**周期性重启**(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. 理论那么难,工程上真的解得动吗 ===== | ||
| + | |||
| + | 解得动,而且常被低估。原因是**最坏情况**和**实际实例**是两回事: | ||
| + | |||
| + | * 工业实例大多来自电路、程序、配置这类**有结构**的问题,CDCL 学习出的子句正好抓住这些结构 | ||
| + | * 现代求解器能处理**百万级变量、千万级子句**的实例;SAT Competition 的工业组就是拿真实 EDA / 验证问题当题面 | ||
| + | * 求解前还有成体系的**预处理**(变量消除、子句化简、等价变量合并),先把问题缩小再动手 | ||
| + | * 反过来说:**无结构的随机 3-SAT 依然很难**,接近相变阈值的地方尤其硬 —— 这才是「SAT 太慢」的真实来源 | ||
| + | |||
| + | 一句话:**SAT 的难度不在规模,在结构。** | ||
| + | |||
| + | ===== 8. SAT 用在哪里 ===== | ||
| + | |||
| + | ^ 领域 ^ 在做什么 ^ 为什么落到 SAT ^ | ||
| + | | 硬件形式验证 | 等价性检查、模型检查、BMC | 「两个电路在任意输入下输出相同」本身就是布尔公式 | | ||
| + | | 软件验证 | 限界模型检查、符号执行、测试生成 | 把路径条件编成 CNF,有解即存在触发该路径的输入 | | ||
| + | | SMT / 程序验证 | 合约检查、类型推断、漏洞检测 | 在 SAT 之上加算术等理论('' | ||
| + | | 自动规划 | SATPLAN 一类规划器 | 把「第 t 步执行什么动作」编成变量,约束编成子句 | | ||
| + | | 依赖解析 | 包管理器选版本 | 版本约束本质是布尔组合问题(见下) | | ||
| + | | 配置与排产 | 特性开关、装箱、排课、调度 | 大量互斥 / 蕴含约束,天然是 CNF | | ||
| + | | EDA | 布局布线、时序与功耗约束 | 布尔约束 + 优化目标(MaxSAT) | | ||
| + | | 谜题与游戏 | 数独、N 皇后、扫雷、图着色 | 经典教学案例:把规则写成子句即可 | | ||
| + | | 密码分析 | 对简化轮数密码搜原像 / 碰撞 | 密码本身可展开成布尔电路,求解器即搜索器 | | ||
| + | | 模型计数 | #SAT / 概率推断 | 数解的个数,属 #P 难度 | | ||
| + | | 配置修复 | MaxSAT | 找「改动最小且满足全部硬约束」的方案 | | ||
| + | |||
| + | 包管理器那条多解释一句:**「装 A 需要 B ≥ 2 且 C < 3,而 B ≥ 2 恰与 C < 3 互斥」** —— 这就是一个布尔约束求解问题。Dart 的 '' | ||
| + | |||
| + | ===== 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** = Scholastic Assessment Test,美国大学入学考试(总分 400–1600) | ||
| + | * **SAT** = Site Acceptance Test,工程交付里的**现场验收测试**,与 FAT(Factory Acceptance Test,出厂验收)配对 | ||
| + | |||
| + | ===== 10. 常见坑 ===== | ||
| + | |||
| + | ^ 现象 ^ 原因 ^ 处理方向 ^ | ||
| + | | 求解器返回 UNKNOWN 就当无解 | UNKNOWN 只是「没在预算内算完」 | 放宽时限、调参数、换求解器;别把三态压成两态 | | ||
| + | | 拿纯 SAT 求解器去解明显是整数规划的问题 | 硬把整数编码成布尔,变量爆炸 | 直接上 SMT 或专用求解器 | | ||
| + | | CNF 文件头数字与内容不符 | '' | ||
| + | | 编码完变量一大就解不动 | 「恰好一个」用了 O(n²) 两两互斥 | 换顺序 / commander 编码 | | ||
| + | | UNSAT 结果无法复核 | 没保留证明 | 让求解器输出 DRAT,用校验器独立验证 | | ||
| + | | 随机实例解不动,就断言「SAT 不行」 | 随机 3-SAT 本身就是最难的一类 | 换建模方式,减少对称性 | | ||
| + | | 换个求解器后模型不同 | 求解顺序受启发式影响 | 把 SAT / UNSAT 当结论,模型按需解读 | | ||
| + | | 把 SAT 与 SMT 混着说 | 口语化简写 | 明确写「布尔 SAT」还是「SMT」 | | ||
| + | |||
| + | 倒数第二条展开一句:**同一个公式,不同求解器、不同版本给出的模型可能完全不同,但 SAT / UNSAT 的结论必须一致。** 若结论不一致,那是求解器或编码的 bug,不是「口味问题」。 | ||
| + | |||
| + | ===== 11. 一句话总结 ===== | ||
| + | |||
| + | > SAT 就是问「**存不存在一组真假取值,让这个布尔公式为真**」:答「存在」给一个赋值(模型),答「不存在」给一份可校验的证明。它是历史上第一个被证明的 **NP 完全**问题(Cook–Levin 1971),却是工程上最成功的「难问题」之一 —— CDCL 求解器能从冲突中学习,把电路、程序、依赖关系这类**有结构**的问题解到百万变量规模。看到代码或工具里的 '' | ||
| + | |||
| + | 相关:[[代码术语: | ||
| + | |||
| + | ---- | ||
| + | |||
| + | 返回:[[代码术语]] | ||
| + | |||
| + | ```mdk height=600 color=# | ||
| + | # 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) | ||
| + | - # | ||
| + | - 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 让有结构的工业实例真的可解 | ||
| + | ``` | ||