知识卡片
枚举赋值不证明指数下界
有k个电路输入时,朴素判定法最多枚举2ᵏ组赋值;这只给出一个指数级算法,不能证明不存在更快算法。
要证电路可满足性NP完全,还需证明每个NP语言可多项式归约到它。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Given a circuit C, you can determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if the circuit has k inputs, then you would have to check up to 2k possible assignments. When the size of C is polynomial in k, checking all possible assignments to the inputs takes Ω(2k) time, which is superpolynomial in the size of the circuit.10 In fact, as we have claimed, there is strong evidence that no polynomial-time algorithm exists that solves the circuit-satisfiability problem because circuit satisfiability is NP-complete. We break the proof of this fact into two parts, based on the two parts of the definition of NP-completeness. Lemma 34.5 The circuit-satisfiability problem belongs to the class NP. Proof We provide a two-input, polynomial-time