知识卡片

普通读书笔记卡 · 3714.b

NP完全兼属NP且至少同样难

理解等级:中级

NP完全问题既属于NP,又在多项式归约意义下不比NP中任何问题容易。

只要一个NP完全问题有多项式时间算法,就会得到P=NP;目前不能把尚未找到算法等同于证明它不存在。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[5000,10000))。 - 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与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