To P or not to P——这是最伟大的计算机数学问题

2000年5月24日，新罕布什尔州的克莱数学研究所列出了数学和计算机科学中七个未解决的问题。解决其中任何一个问题的奖励是该研究所提供的一张100万美元的支票。然而，直到今天，这些问题中只有一个被解决了，那就是庞加莱猜想（Poincaré Conjecture）——被俄罗斯数学家格里戈里-佩雷尔曼解决。重要的是要认识到，这些问题的 "解 "是以数学证明的形式出现的，要么否认，要么确认该定理。其他六个未解决的问题之一是著名的P vs NP问题。

时间复杂度

对时间复杂度的研究可以得到很好的复杂度（下面解释）。麻省理工学院的迈克尔·西普塞（Michael Sipser）教授因其在计算复杂性理论领域的杰出工作而闻名，他给出的标准定义是：
让M是一个确定性的图灵机（ Turing machine），它对所有的输入上都会停机（halt，停机问题是逻辑学的焦点，也是第三次数学危机的解决方案）。M的运行时间或时间复杂度是函数f：N→N，其中f(n)是M对任何长度为n的输入所使用的最大步骤数。习惯上我们用n来表示输入的长度。
看完定义应该比较懵逼吧？这到底是什么意思呢？现在，让我们降低维度来看这个问题。一个算法的时间复杂度可以被描述为该算法在计算机上对给定输入长度的运行时间。确定一个给定程序的时间复杂度可能很困难，所以计算机科学家们开发了一种称为渐近分析（asymptotic analysis）的估计表达式，也称为大O表示。做好准备，另一个复杂的定义正在向你走来：
让f和g是函数f , g : N → R+。如果存在正整数c和n0，使每个整数n≥n0，f(n)≤cg(n)，则称f(n)=O(g(n))。
当f(n)=O(g(n))时，我们说g(n)是f(n)的上限，或者更准确地说，g(n)是f(n)的渐近上限，以强调我们在抑制常数因素。
让我们暂时跳过第一部分，更仔细地看一下定义的第二部分。我们将在这里使用一个例子：
  • 一个简单的C语言for循环
为了找到这个算法的渐进上限，我们必须首先分析各部分。如果本例中数组n的大小为10，则循环将运行10次。在这种情况下，函数的上限将永远是n的大小。因此，n是渐进的上限，计算机科学家用来描述这一事实的符号是O(n)，这被称为线性时间（ linear time）。
  • 两个for循环的 大O是O(n^2)
这里的函数有两个for循环，意味着如果n=10，它将被运行100次，或n*n次。大O的表达是O(n^2)，或者说是平方时间（quadratic time）。
假设一个算法，我们能够确定其时间复杂度为f(n)=4n²+2n+12，这是否意味着大O将是O(4n²+2n+12)？重要的是再看一下定义的最后一部分，我们正在寻找渐近线，因此我们只需要增速最快的项（在这种情况下是4n^2），并且我们去掉常数（因为常数可以根据硬件差异和限制而改变），最终得到一个O(n²)的大O。
那么这与上面简单的两个for循环具有相同的大O？是的！大O帮助计算机科学家可视化算法运行时间的上限，所以就所有目的而言，这两种不同的算法具有相同的大O。
下面是一些不同的大O复杂度的相互比较：

P类和NP类

现在我们对时间复杂度有了一定的了解，我们终于可以看看研究判定问题（ decision problems）的P和NP了。判定问题是一个有答案 "真 "或 "假 "的问题。
P：P代表多项式，是两者中比较简单的。P类可以被描述为可由算法在多项式时间内解决的问题的集合。
  • O(n), O(n^2), O(n^3) 都是多项式时间的例子。
  • 属于P类的问题的例子包括乘法，或者寻找一个数组中最大的整数。
NP：NP代表非确定性多项式，这是两类中比较复杂的，它有两种不同的可能定义。更简单的定义是。
在计算复杂性理论中，NP（非确定性多项式时间）是一个用于对决策问题进行分类的复杂性类。NP是一组决策问题，对于这些问题，答案是“是”，它的证明可以在多项式时间内被确定性图灵机证明。
NP（Nondeterministic Polynomially，非确定性多项式）类问题是指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。
最好是看一个经典游戏来帮助直观地了解NP问题。
例子：数独
数独是我用来描述NP中问题类别的最常用的例子。
  • 一个正在被算法解决的数独谜题
数独是很容易解决的，所以上面的算法并没有花费多少时间来解决它。然而，如果这个数独谜题从9x9增长到100x100呢？如果我们把数独问题从9x9的输入，概括为采取NxN，那么这个问题很快就会变成一个NP问题。
数独问题是很容易验证的。这意味着，给定一个数独问题的解，存在一个多项式时间的算法，可以正确验证该解是否正确。
  • 一个已解决的数独谜题
再次使用这个9x9的例子，你自己可以很容易地验证这是否是一个正确的解，并且设计一个算法来完成你自己的大脑在这种情况下所能完成的工作也是很简单的。然而，要解决任何大小的数独谜题的算法似乎就不那么简单了，这也是事实。
更深入的研究：NP的完备性（完全性）
与NP相关的问题是NP的完备性问题。这些问题因其难度而闻名，因为它们没有已知的多项式算法解（O(n), O(n^2)...）。这些问题可以被认为是计算机科学中最棘手的问题。
  • 在O(n)中运行100个元素要1秒的算法，在O(n³)中运行要3个小时。这似乎是一个很大的跳跃，一个以O(2^N)运行的问题，100个元素需要300quintillion（百万的3次方）年。因此，寻找一个多项式解比一个指数解更有价值。
确定一个问题是否是NP-完备性的过程如下。
  1. 确定问题是否在NP中（可在多项式时间内验证或可由非确定性图灵机解决）。
  2. 确定该问题是否是NP-Hard。
NP-Hard：当事情从复杂变成更复杂。
NP-Hard问题的定义如下：
非正式地讲，NP-Hard问题与任何NP问题一样难或更难。更确切地说，任何NP-完备性问题都可以在多项式时间内简化为NP-Hard问题。
解决一个NP-Hard问题的算法可以解决所有的NP-Hard问题，因为每个NP-Hard问题都可以被转化成其他问题。这意味着解决一个NP-完备问题的方案也能解决所有其他NP-完备问题。
同样值得注意的是，一个NP-Hard问题不一定在NP中（记住），如果它既是NP-Hard又在NP中，我们会把它归类为NP完备，而且不一定是判定问题。
例子：路径与总和
哈密顿路径问题（Hamiltonian Path problem）问的是对于一个给定的图，是否有一条路径只访问每个顶点一次。
  • 哈密顿路径
哈密尔顿路径问题是一个NP完备性问题的例子。要验证这个问题是否在NP中很简单。
  1. 检查每个顶点。
  2. 如果没有通往某个顶点的路径，则返回false。否则返回true。
子集和（Subset Sum problem）问题是，给定一个包含整数的集合S和一个目标和（target-sum）N，确定S中是否有一个子集的总和为N。
  • S={1，3，5，6}，N=4。答案是 "真"，因为子集{1，3}的总和为4。
这个问题也是NP完备的。要验证这个问题是否属于NP，比上一个问题还要简单：
  1. 将子集中的数字相加。
  2. 如果它们等于N，则返回true。否则返回false。
也许你很难相信，但是子集和问题和哈密顿路径问题在函数上是等价的，因为它们都是NP-完备的。这意味着子集之和的解决方案可以转化为解决哈密尔顿路径问题。有大量的NP-完备问题，这只是其中两个例子。

最后：P=NP？

P是否等同于NP？
大多数数学家和计算机科学家会说，No。但我们还没有一个明确的证明。
  • 普遍的共识是左边的说法是正确的
重要的是要考虑到，P=NP只告诉我们存在多项式时间的解，而不是这些算法是什么。
然而，如果这些算法确实存在，而且问题被解决了，那么它不仅对计算机科学领域，而且对其他主要领域都会产生一些深远的影响：
  • 公钥加密，或者说我们几乎所有的个人和可识别数据是如何被存储和保护的。
  • 加密哈希，或者说很多信息是如何被加密的，以及像比特币这样的系统是如何被保护的。
  • 计算基因组学，这个领域的一系列问题。
其影响可能是巨大的，因为到最后，我们实际发现最可用的算法希望是O(n)或O(nlogn)和O(logn)--即使P=NP，如果算法是O(n^100)，它也没什么实际意义。
这是一个我们仍在努力解决的问题，也是一个也许永远不会被解决的问题。

总结

  • P类问题：所有可以在多项式时间内求解的判定问题构成P类问题。
  • NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。
  • NP-hard，指所有NP问题都能在多项式时间复杂度内归遇到的问题。
  • NP完备问题（简单的写法是 NP=P？）：NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法，那么所有NP问题都是多项式时间可解的。这些问题被称为NP-完备问题（NPC问题）。
赞 (0)

相关推荐