SAT
Boolean Satisfiability Problem
NP 完全之祖 · 一切约束求解的起点
- 定义
- SAT（Boolean Satisfiability Problem）是网络安全领域的专业术语。SAT（Boolean Satisfiability Problem）是计算机科学中第一个被证明为 NP 完全的问题：给定一个布尔公式，判断是否存在一组变量赋值使公式为真。
最后更新：2026-06-16
什么是SAT？
SAT（Boolean Satisfiability Problem）是计算机科学中第一个被证明为 NP 完全的问题：给定一个布尔公式，判断是否存在一组变量赋值使公式为真。SAT 求解器是 SMT 求解器的核心引擎，也是符号执行、模型检验、形式化验证等技术的底层基础。
- 第一个被证明为 NP 完全的问题（Cook-Levin 定理）
- SMT 求解器的核心引擎
- 现代 SAT 求解器可处理数百万变量的实际问题
SAT详解
SAT 问题的输入通常是 CNF（合取范式）形式的布尔公式：多个子句的 AND，每个子句是若干文字的 OR。例如 (x₁ ∨ ¬x₂) ∧ (x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₃)。虽然 SAT 理论上是 NP 完全的（最坏情况指数时间），但现代 SAT 求解器（如 MiniSat、CaDiCaL）通过 DPLL/CDCL 算法和大量启发式优化，在实际问题上表现极好，能处理工业级规模的实例。在二进制安全中，SMT 求解器内部将位向量/算术约束最终编码（bit-blasting）为 SAT 问题交给 SAT 引擎求解。
公式提示
CNF 示例：(x₁ ∨ ¬x₂) ∧ (x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₃)，问是否存在 x₁,x₂,x₃ 的赋值使整体为 true
SAT的应用场景
正式定义
判断给定布尔公式是否存在使其为真的变量赋值的判定问题，是计算复杂性理论中第一个 NP 完全问题
应用场景
- SMT 求解器的底层引擎（bit-blasting 后归约为 SAT）
- 硬件电路等价性验证
- 模型检验中的状态空间搜索
- 密码学中的约束求解攻击
常见误区
- NP 完全不等于不可解——现代 SAT 求解器在实际问题上极其高效
- SAT 不只是理论概念——工业界每天在用 SAT 求解器验证芯片、分析软件
- SAT 和 SMT 不是竞争关系——SMT 在上层提供更丰富的表达力，底层仍调用 SAT
实际案例
📌 CDCL 算法
现代 SAT 求解器的核心算法——冲突驱动子句学习（Conflict-Driven Clause Learning）。当搜索遇到冲突时学习新子句剪枝，使求解效率提升数量级。
📌 Bit-blasting
SMT 求解器将位向量约束（如 32 位加法）展开为等价的布尔公式，交给内部 SAT 引擎求解。一个 32 位变量展开为 32 个布尔变量。
SAT的参考来源
关于SAT的常见问题
- SAT 问题是什么
- 给定一个布尔公式，判断是否存在一组变量赋值使其为真。是第一个被证明为 NP 完全的问题，也是 SMT 求解的理论基础。
- SAT 和 SMT 有什么关系
- SMT 在 SAT 基础上扩展了算术、位向量等理论。SMT 求解器内部通常将高级约束编码为 SAT 问题（bit-blasting），再调用 SAT 引擎求解。
- SAT 既然是 NP 完全为什么还能用
- NP 完全是最坏情况。现代 SAT 求解器通过 CDCL 算法和启发式优化，在实际工业问题上可高效处理数百万变量。