每周学点大数据 | No.6算法的分析之易解问题和难解问题

No.6期

算法的分析之易解问题和难解问题

小可：嗯，我懂了。可是您前面说现在的计算机在模型上都可以称作图灵机，这个要如何理解呢？

Mr. 王：你能思考这个问题是非常好的。其实现在电子计算机可以解决的所有问题，都可以用图灵机解决，就用2+3 这个例子，我们一开始将“算式”写在纸带上，相当于“输入”；图灵机的执行过程相当于计算机对问题进行处理；留在纸带上的结果相当于“输出”；状态转换图，相当于计算机程序；纸带在执行过程中相当于内存，读写头一部分是CPU，同时也是读写内存的设备。

小可恍然大悟，说：这么一说，好像确实和计算机挺像的。

Mr. 王：好，既然你初步理解了什么是图灵机，我们就来说说什么是易解问题和难解问。前面我们提到过多项式时间。如果一个问题可以用确定状态图灵机（DTM）在多项式时间界限内解决的话，我们称之为P问题；如果一个问题可以用不确定状态图灵机（NTM）在多项式时间界限内解决的话，我们称之为NP问题。

在这里，所谓的确定状态就是说如果在每一种状态下接收到一个特定的输入，它都会执行固定的状态转换和动作，这就是确定状态图灵机；反之，如果在某一种或多种状态，对于某一个输入，它可能产生多种不同的状态转换，这就是不确定状态图灵机。而计算机只能表达确定状态图灵机，无法表达不确定状态图灵机，所以我们用计算机去解决NP问题的时间界限往往是指数的。

有这样一类问题，首先它是NP问题，其次所有的NP问题都可以归约为它，我们称之为NP完全问题（NP-complete）。

小可：什么是归约呢？

Mr. 王：简单来说，如果找到了解决问题A的办法，那么问题B也就得到了解决，而且正可以用解决问题A的那种办法。那么我们说，B可以归约为A。从这里可以看出，B可以归约为A，说明A要比B 难以解决，或者说A比B难。

小可：哦，原来是这样，那么NP 完全问题就是NP 问题中最难的那些问题了？

Mr. 王：你说得对。还有一类问题，所有的NP问题都可以归约为它，但我们还无法判定它是不是NP问题。我们将这类问题称为NP难问题（NP-hard）。

小可：也就是说，我们还确定不了不确定状态图灵机能不能在多项式时间界限内解决它，那说明它的难度有可能比NP完全问题更高吧。那是不是说，如果我们恰好证明了一个NP 难问题是NP问题的话，那么它就是NP完全问题了？

Mr. 王：是的，这说明你对NP问题的定义已经有了很好的了解。了解了这几类问题，我们不难发现有P ⊆ NP，也就是说，P问题都是NP问题。这是因为我们可以把确定状态图灵机看作不确定状态图灵机的一种特殊形式，只不过它的所有转换都是确定的，也就是说，所有的转换概率都是1。

小可：嗯，的确是这样，P问题都是NP问题。

Mr. 王：现在困扰计算机科学界最大的问题就是P是否等于NP，这个问题被提出了多年，影响着很多问题的研究，至今未能得到解决。显然有P包含于NP，但到目前为止NP是不是包含于P还不能确定。如果这个问题得到了证明，就说明P=NP。在计算机科学界里，大量的疑团都指向P是否等于NP。如果P=NP，那么现在很多科学研究的结论将会被改写，很多新的结论也会被提出。但是证明这个问题是非常非常难的，当然，也有可能最后证明的结果是P不等于NP。要证明P=NP，就需要计算机科学界的学者们多多努力了。

好了，现在我们来给问题的难度排个序。首先有P包含于NP，所以在难度上P≤NP。由于NP完全问题是NP问题中最难解决的，故NP完全问题会难于一般的NP问题，所以有P≤NP≤NPcomplete。由于NP-hard 和NP-complete同属的所有NP类都可以归约为它们的这种问题， 而NP-hard还不能确定是不是NP 问题， 所以它应该更难一些， 所以有P≤NP≤NPcomplete≤NPhard。我们一般认为P问题是易解问题，而NP-complete以上的就是难解问题。

P-NP问题的关系

小可：嗯，我懂了。

Mr. 王：不过进入了大数据时代以后，易解和难解问题又相应地发生了一些变化，当数据规模并没有那么大的时候，多项式算法在求解很多问题时，算法的实际运行时间或许我们还可以接受，我们认为多项式算法还算是好的算法，能用多项式算法解决的问题还算是易解问题；但当数据量真的大到可以称之为“大数据”的时候，多项式算法的实际运行时间也会变得非常长，变得我们难以接受，这样多项式算法就已经不能满足我们对于很多大数据规模的问题求解。有时一个问题虽然是P问题，但是由于数据规模太大，也变得很难以解决，甚至当输入规模特别大的时候，在很多情况下就连线性算法也难以满足需求了。有些时候，我们就不得不去设计一些后面要讲的亚线性算法来匹配这些非常大的数据集合，以满足我们对它的速度要求。

小可：那有没有更快的算法？比如其运行时间与输入的数量级完全无关，如就是个常数项c呢？也就是说，这个算法不论输入n多大，它的运行时间都是一个特定的常数t呢？

Mr. 王：这样的时间界限记为O(1)，我们称之为常数时间算法，这样的算法一般来说是最快的，因为它与输入规模完全无关，不论输入规模n多么大，我们都可以用一个与输入规模n无关的常数时间得出结论，相比于巨大的n来说，这个常数在数量级上已经微乎其微了。

小可：哦，这也体现了只关心数量级，而不关心具体数值的思想。

内容来源：灯塔大数据