知识卡片
NP完全问题入P则P等于NP
若L为NP完全且L∈P,任意L′∈NP都能归约到L,再用L的算法便可多项式时间判定L′。结合P⊆NP,得到P=NP。
这是条件命题,不预设当前已经找到该算法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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