知识卡片
公式可满足性由电路归约证明
SAT问布尔公式是否存在使其值为1的变量赋值。
赋值可多项式时间验算,故SAT∈NP;再把任意电路转成等可满足的公式,得到CIRCUIT-SAT≤ₚSAT,结合已知起点得SAT为NP完全。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Theorem 34.9 Satisfiability of boolean formulas is NP-complete. Proof We start by arguing that SAT ∈ NP. Then we prove that SAT is NP-hard by showing that CIRCUIT-SAT ≤P SAT, which by Lemma 34.8 will prove the theorem. To show that SAT belongs to NP, we show that a certificate consisting of a satisfying assignment for an input formula ϕ can be verified in polynomial time. The verifying algorithm simply replaces each variable in the formula with its corresponding value and then evaluates the expression, much as we did in equation (34.2) above. This task can be done in polynomial time. If the expression evaluates to 1, then the algorithm has verified that the formula is satisfiable. Thus, SAT belongs to NP. To prove that SAT is NP-hard, we show that CIRCUIT-SAT ≤P SAT. In other words, we