知识卡片

普通读书笔记卡 · 3714.b.5

NP难与NP完全差在自身归属

理解等级:中级

若NP中每个语言都能多项式归约到L,则L为NP难;再加上L自身属于NP,才称NP完全。

证明新问题NP完全时,两项条件都需核对,只有归约到它不足以说明它有多项式证书验证器。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      A language L ⊆ {0, 1}* is NP-complete if L ∈ NP, and L′ ≤P L for every L′ ∈ NP. If a language L satisfies property 2, but not necessarily property 1, we say that L is NP-hard. We also define NPC to be the class of NP-complete languages. As the following theorem shows, NP-completeness is at the crux of deciding whether P is in fact equal to NP. Theorem 34.4 If any NP-complete problem is polynomial-time solvable, then P = NP. Equivalently, if any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable. Figure 34.6 How most theoretical computer scientists view the relationships among

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[45000,50000))。 - 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。 - 原始内容:A language L ⊆ {0, 1}* is NP-complete if L ∈ NP, and L ′ ≤ P L for every L ′ ∈ NP. If a language L satisfies property 2, but not necessarily property 1, we say that L is NP-hard . We also define NPC to be the class of NP-complete languages. As the following theorem shows, NP-completeness is at the crux of deciding whether P is in fact equal to NP. Theorem 34.4 If any NP-complete problem is polynomial-time solvable, then P = NP. Equivalently, if any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable. Figure 34.6 How most theoretical computer scientists view the relationships among