月度归档:2017年02月

P和NP问题(P versus NP problem)

点击量:2687

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

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

什么是NP问题?
对有些问题而言,并不存在一个已知的多项式时间内的算法来解决问题,但是如果有人能够提供一个答案(不论对错),我们却能够很快地验证这个解是否正确,那么这些能够在多项式时间内验证一个解的问题被称为NP问题。通俗,不严谨的讲就是能在多项式时间内猜出解的问题。举个栗子:著名的子集合求和问题(subset sum problem),给定一个整数集合:{−2, −3, 15, 14, 7, −[……]

继续阅读