知识卡片

普通读书笔记卡 · 1708.b.2.i · 生成模型:未记录

未知多项式算法不定义完全性

理解等级:中级

NP完全首先是问题类与归约关系:一个判定问题属于NP,且NP中的每个问题都能多项式时间归约到它。这里的判定问题只回答是否存在满足条件的解,NP所需的证据可在多项式时间验证。

“还不知道多项式算法”本身不是完全性的定义。多项式时间也不限O(n²),可为某个固定次数的多项式上界。旅行商的判定版本与求最短路线的优化版本应区分,不能都不加限定称NP完全。

上述边界按Stephen Cook的官方问题说明核对;Clay问题页访问时仍列P与NP关系为未解决。不据此声称已证明所有实例困难或任何精确方法都不可能。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      NP完全问题 没有已知的求解多项式时间的算法,但也无法证明此多项式不存在,这类问题称为NP完全问题。所以,长久以来NP完全问题一直是计算机科学领域令人困惑和烦恼的问题之一。多项式时间算法的复杂度小于或等于O(n2),其中k是常数。很多有用且看似困难的问题都归为此类,例如:旅行商问题(见第16章)。

    参考来源

    - 位置:《算法精解:C语言描述》第4章《相关主题》(spine1203;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1171.html;u046-ch04-010)。 - 结论依据:46完整NP段确有定义/多项式次数与旅行商的过宽表述;已读Clay所载Cook定义4和归约条件并查当前问题页纠正,属于修复书内必要准确性,不新增未见应用或证明。 - 原始内容:NP完全问题 没有已知的求解多项式时间的算法,但也无法证明此多项式不存在,这类问题称为NP完全问题。所以,长久以来NP完全问题一直是计算机科学领域令人困惑和烦恼的问题之一。多项式时间算法的复杂度小于或等于O(n2),其中k是常数。很多有用且看似困难的问题都归为此类,例如:旅行商问题(见第16章)。