知识卡片
NP难与NP完全差在自身归属
若NP中每个语言都能多项式归约到L,则L为NP难;再加上L自身属于NP,才称NP完全。
证明新问题NP完全时,两项条件都需核对,只有归约到它不足以说明它有多项式证书验证器。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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