首页 > 代码库 > 关于P和NP

关于P和NP

只要对算法稍有兴趣的人,总会多多少少的遇到P和NP这两个概念,而大部分书上似乎都默认大家知道这是怎么回事一样,而我恰好又不知道。

其实在我的记忆中,我已经很多次在网上查询这两个概念了,只是遗忘是可怕的……

好吧,今天想再次去搞清楚这两个概念。

在wiki上从这两个概念可以引申出很多我陌生有熟悉的概念。

多少写一些,增强一下记忆,对于在wiki上的链接就不贴了,概念太多。

这两个概念是来形容问题的,也就是说,某个问题是P的,或者NP的,即“……的问题”。

而这里是针对解决问题的算法来说的,也就是说,不管是P还是NP,都是“……的算法的问题”。

我们看到P和NP里面都有P,这个P就是多项式(polynomial)时间,说道这两个概念,应该都是“……多项式时间……的算法的问题”。补充一下,多项式时间,是一种时间测度,通常多项式时间不会随着参数的变化而发生剧烈的变化,当然高次还是很可怕的。

有了上面的理解,我们大致可以认为:

  1. P就是有多项式时间算法可解决的问题
  2. NP就有些搞了,说是有多项式时间可验证的问题

当然,上述都是在确定行图灵机上。我喜欢上面这个定义,很直观。

看,我上面说得很含糊,其实还有一个对比定义P和NP的说法:

  1. NP - 在非确定性图灵机上有多项式时间算法的问题
  2. P - 在确定性图灵机上有多项式时间算法的问题

我不太喜欢上面这个说法,是因为我还要去了解“确定性图灵机”和“非确定性图灵机”,真是个悲伤的结局……

 补充一个链接 http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html

关于P和NP