知识卡片
NP完全兼属NP且至少同样难
NP完全问题既属于NP,又在多项式归约意义下不比NP中任何问题容易。
只要一个NP完全问题有多项式时间算法,就会得到P=NP;目前不能把尚未找到算法等同于证明它不存在。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Informally, a problem belongs to the class NPC—and we call it NP-complete—if it belongs to NP and is as “hard” as any problem in NP. We’ll formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to