← 返回刚才阅读的位置

知识卡片

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

NP完全问题入P则P等于NP

理解等级:高级

若L为NP完全且L∈P,任意L′∈NP都能归约到L,再用L的算法便可多项式时间判定L′。结合P⊆NP,得到P=NP。

这是条件命题,不预设当前已经找到该算法。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 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 P, NP, and NPC. Both P and NPC are wholly contained within NP, and P ∩ NPC = Ø. Proof Suppose that L ∈ P and also that L ∈ NPC. For any L′ ∈ NP, we have L′ ≤P L by property 2 of the definition of NP-completeness. Thus, by Lemma 34.3, we also have that L′ ∈ P, which proves the first statement of the theorem. To prove the second statement, consider the contrapositive of the first statement: if P

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[45000,50000))。 - 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。 - 原始内容: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 P, NP, and NPC. Both P and NPC are wholly contained within NP, and P ∩ NPC = Ø. Proof Suppose that L ∈ P and also that L ∈ NPC. For any L ′ ∈ NP, we have L ′ ≤ P L by property 2 of the definition of NP-completeness. Thus, by Lemma 34.3, we also have that L ′ ∈ P, which proves the first statement of the theorem. To prove the second statement, consider the contrapositive of the first statement: if P