知识卡片

普通读书笔记卡 · 3714.b.3.b.2

枚举赋值不证明指数下界

理解等级:中级

有k个电路输入时,朴素判定法最多枚举2ᵏ组赋值;这只给出一个指数级算法,不能证明不存在更快算法。

要证电路可满足性NP完全,还需证明每个NP语言可多项式归约到它。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[55000,60000))。 - 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。 - 原始内容: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 2 k possible assignments. When the size of C is polynomial in k , checking all possible assignments to the inputs takes Ω(2 k ) 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