差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
| 代码术语:sat [2026/10/16 12:31] – 撰写 SAT(布尔可满足性问题)词条 张叶安 | 代码术语:sat [2026/10/16 12:32] (当前版本) – 为 SAT 词条添加全文结构思维导图 张叶安 | ||
|---|---|---|---|
| 行 292: | 行 292: | ||
| 返回:[[代码术语]] | 返回:[[代码术语]] | ||
| + | |||
| + | ```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 让有结构的工业实例真的可解 | ||
| + | ``` | ||