设计与分析 P 级和 NP 级

在计算机科学中，解决许多问题的目标是最大化或最小化某些值，而在其他问题中，我们试图找出是否存在解决方案。因此，问题可以分类如下 -

最优化问题

优化问题是那些目标是最大化或最小化某些值的问题。例如，

有许多问题的答案是“是”或“否”。这些类型的问题称为决策问题。例如，

每个决策问题只能有两个答案，是或否。因此，如果决策问题为特定输入提供“是”的答案，则该决策问题可能属于一种语言。语言是答案为“是”的输入的总和。前面几章讨论的大多数算法都是多项式时间算法。

对于输入大小n，如果算法的最坏情况时间复杂度为O(n ^k )，其中k是常数，则该算法是多项式时间算法。

矩阵链乘法、单源最短路径、全对最短路径、最小生成树等算法在多项式时间内运行。然而，存在许多问题，例如旅行推销员、最佳图着色、哈密顿循环、查找图中最长路径以及满足布尔公式，而尚无已知的多项式时间算法。这些问题属于一类有趣的问题，称为NP 完全问题，其状态未知。

在这种情况下，我们可以将问题分类如下 -

P类由那些可以在多项式时间内解决的问题组成，即这些问题可以在最坏情况下在时间O(n ^k )内解决，其中k是常数。

这些问题称为易处理问题，而其他问题则称为棘手问题或超多项式问题。

形式上，如果存在多项式p(n)使得该算法可以在O(p(n))时间内解决大小为n的任何实例，则该算法是多项式时间算法。

对于大n来说，需要Ω(n ⁵⁰ )时间来解决的问题本质上是棘手的。大多数已知的多项式时间算法在k值相当低的情况下运行时间为O(n ^k )。

考虑多项式时间算法类别的优点在于，所有合理的确定性单处理器计算模型都可以用最多一个多项式慢速模型相互模拟

NP 类由可在多项式时间内验证的问题组成。NP 是一类决策问题，借助一些额外信息，很容易检查所声称答案的正确性。因此，我们并不是在寻求一种找到解决方案的方法，而只是为了验证所谓的解决方案是否确实正确。

此类中的每个问题都可以使用穷举搜索在指数时间内解决。

每个可以通过确定性多项式时间算法解决的决策问题也可以通过多项式时间非确定性算法解决。

P 中的所有问题都可以用多项式时间算法解决，而NP - P中的所有问题都很难解决。

尚不清楚是否P = NP。然而，许多已知的NP问题都具有这样的性质：如果它们属于P，那么就可以证明P=NP。

如果P ≠ NP，则 NP 中存在既不在 P 中也不在 NP 完全中的问题。

如果很容易找到问题的解决方案，则该问题属于P类。如果很容易检查可能非常繁琐的解决方案，则该问题属于NP 。