代码术语:sat

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

后一修订版
前一修订版
代码术语:sat [2026/10/16 12:29] – 创建 张叶安代码术语:sat [2026/10/16 12:32] (当前版本) – 为 SAT 词条添加全文结构思维导图 张叶安
行 1: 行 1:
-1+====== 一文讲清楚: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 让有结构的工业实例真的可解 
 +``` 

该主题尚不存在

您访问的页面并不存在。如果允许,您可以使用创建该页面按钮来创建它。

  • 代码术语/sat.1792124994.txt.gz
  • 最后更改: 2026/10/16 12:29
  • 由 张叶安