知识卡片
未知多项式算法不定义完全性
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章)。