P和NP问题(P versus NP problem)

Hits: 1718

P和NP问题(P versus NP problem)
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题,它也是克雷数学研究所七个千禧年大奖难题之一。学计算机的肯定会经常听到P和NP,但我相信很多人跟我一样对这个问题既熟悉又陌生,并不能真正地把他理解透彻,今天花点时间总结下吧。

什么是P问题?
能够在多项式时间内给出答案的问题被称为P问题,也就是说存在一个多项式时间复杂度内的算法解决该问题。这个很好理解,那为什么要是在多项式时间呢?因为只有在多项式时间内的复杂度才是计算机所能接受的,再大的复杂度(比如指数级,阶乘级别)即使有解也没有实际价值(计算量太大)。

什么是NP问题?
对有些问题而言,并不存在一个已知的多项式时间内的算法来解决问题,但是如果有人能够提供一个答案(不论对错),我们却能够很快地验证这个解是否正确,那么这些能够在多项式时间内验证一个解的问题被称为NP问题。通俗,不严谨的讲就是能在多项式时间内猜出解的问题。举个栗子:著名的子集合求和问题(subset sum problem),给定一个整数集合:{−2, −3, 15, 14, 7, −10} ,问:是否存在一个非空子集其所包含的元素之和为0?答案当然是存在,比如:子集{−2, −3, −10, 15}的和就为0。这个问题可以在多项式时间内验证答案,但是不能给出一个多项式时间内的算法来解决问题。别小看这个简单的问题,目前已知的算法只能穷举,复杂度是2的N次方。
对于NP问题有几点说明:

  1. 很明显,所有的P问题都是NP问题,因为如果一个问题能在多项式时间内被解决,那么他一定能在多项式时间内被验证。
  2. NP代表的是Nondeterministic Polynomial Time,非确定性多项式时间,并不是想当然的非P问题,这点很容易混淆。这里解释下为什么要命名为非确定性多项式时间,就是因为不确定这类问题能否在多项式时间内被解决(已知算法的复杂度并不是多项式时间)。
  3. 可以简单理解为很容易验证答案,但是很难给出算法的问题。

P/NP问题
好了,如果你理解了P和NP的概念,那么P/NP问题就很好理解了。P/NP问题讨论的其实是,一个能在多项式时间内被验证答案的问题是否也能在多项式时间内被解决?如果P=NP,则表示一个能在多项式时间内被验证答案的问题也能在多项式时间内被解决。

NP完全问题(NP-completeness)
NP完全问题(NP-completeness)也被称为NPC问题,这个概念是在证明P/NP的过程中被提出来的。这个概念很难理解,看了很多介绍都没有完全理解,直到翻到一篇十年前一个高三学生写的文章才真正理解(人和人的差距怎么这么大)。
首先看他的定义

一个决定性问题C若是为NPC,则代表它对NP是完备的,这表示:

  1. 它是一个NP问题,且
  2. 其他属于NP的问题都可归约成它。

关键在于理解第二点,而要理解第二点首先要理解一个重要的概念:归约(Reducibility)。
可归约在此意指对每个问题L,总有一个多项式时间多对一变换,即一个决定性的算法可以将实例l ∈ L转化成实例c ∈ C,并让c回答Yes当且仅当此答案对l也是Yes。
简单地说,一个问题L可以归约成问题C则表示问题C的解法对问题L是适用的(问题C更通用,可以理解为问题L是问题C的一种特殊情况),也就是说如果解决了问题C,那么问题L也可以用同样的算法被解决。举个简单的例子,我们都知道求解一元二次方程的算法适用于一元一次方程,因为只要把二次项系数设定为0(其实就是转换规则)就能适用于一元一次方程了。这个过程有点像是把小问题不断归约为更一般的大问题,很显然更一般的问题时间复杂度更高,应用的范围也更广。下面摘自matrix67文章里的一段话,我觉得写得非常清晰:

通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC。

看到这段话我也很震惊,居然所有的NP问题都可以规约成同一个NP问题,而且这样的NP问题还不止一个,简直不可思议!!!历史上第一个被证明的NPC是
布尔满足性问题(Boolean Satisfiability Problem),证明过程太复杂了,但这个问题本身还是很简单的,有兴趣可以了解下。正是NP完全问题被发现,才使得人们在P=?NP问题上看到了曙光,因为只要能证明至少存在一个NPC问题能在多项式时间内被解决,那么所有的NP问题都能在多项式时间内被解决,也就证明P=NP了!!但是很遗憾,在目前被发现的21个NPC问题中没有一个被证明可以在多项式时间内被解决,这也是为什么大多数科学家认为P!=NP的原因。读到这里,如果从命名的角度来看NPC的概念就很好理解了,之所以称之为NP完全/完备问题,是因为这类问题包含了所有的NP问题,所以说他是完备的。

如何证明一个问题是NPC问题?
自然根据定义来证明,首先证明这是一个NP问题,其次证明这个问题可由任何一个已知的NPC问题归约而来。那么第一个NPC问题是如何证明的呢?也就是布尔满足性问题的证明,正如之前所说这个证明相对复杂,有兴趣可以去Wikipedia看看。

NP-Hardness
NP困难和NPC的区别在它满足NPC问题定义的第二条但不一定要满足第一条,也就是说所有NP问题都可以归约为它,但它不一定是一个NP问题。也就是说NP困难问题至少跟NPC一样难,因为NP困难问题有可能不是NP问题(也就是说不能在多项式时间内验证答案),所以它有可能比NPC问题更难解决。