NP完全性理论

参考&＃xff1a;《计算机程序设计与分析》

计算机算法理论中&＃xff0c;最深刻的问题之一是&＃xff1a;“从计算的观点来看&＃xff0c;要解决的问题的内在复杂性如何&＃xff1f;”即判断该问题是“易”解决还是“难”解决的。问题的计算复杂性可以通过解决该问题所需计算量的多少来度量&＃xff0c;但要确定一个问题的内在计算复杂性是十分困难的。可以把多项式时间内可以解决的问题看做“易”问题&＃xff0c;将指数函数时间内可以解决的问题看做“难”问题。这里的多项式时间和指数函数时间是针对问题的规模而言的。为了研究“难”问题&＃xff0c;人们提出了“非确定性图灵机计算模型”。通过该模型&＃xff0c;很多问题就可以在多项式时间内求解。

通常对于每一个最优化问题都有一个与之对应的判定问题&＃xff0c;判定问题较最优化问题容易求解。如下面的旅行售货员问题。

设 是一个带权图。图中各边的费用&＃xff08;权&＃xff09;是正数。图的一条周游路线是包括 V 中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员的问题要在图 G 中找出费用最小的周游路线。

与之对应的判定形式的旅行售货员问题可描述如下&＃xff1a;

对于给定的带权图和一个正数 d 。判定形式的旅行售货员问题要求判定图 G 中是否存在总费用不超过 d 的周游路线。

所有可以在多项式时间内求解的判定问题构成 P 类问题。通常解一个问题要比验证问题的一个解困难的多。P类问题是确定性计算模型下的易解问题类&＃xff0c;而 NP类问题是非确定性计算模型下的易验证问题类。

非确定性算法将问题求解分为猜想和验证两个阶段。算法的猜想阶段是非确定性的&＃xff0c;他给出问题的一个猜测&＃xff0c;算法的验证阶段是确定性的&＃xff0c;验证猜想阶段给出的解的正确性。假设算法A是解一个判定问题 Q 的非确定性算法&＃xff0c;如果算法 A 的验证阶段可以在多项式时间内完成&＃xff0c;则称算法 A 是一个多项式时间非确定性算法&＃xff0c;同时也称问题 Q 是非确定性多项式时间可解的。所有非确定性多项式时间可解的判定问题构成 NP 类问题。

从定义可以看出&＃xff0c;大多数科学家认为 &＃xff0c;但一直没有明确的答案。同时存在一类 NPC类问题&＃xff0c;这类问题具备一个重要的性质&＃xff0c;如果一个 NPC 问题可以在多项式时间内解决&＃xff0c;那么 NP 中每一个问题都可以在多项式时间内求解&＃xff0c;即证明&＃xff0c;但目前还没有一个 NPC 问题具备多项式算法。