NP问题

来自 搜狐网 的图片

NP问题是全国科学技术名词审定委员会审定、公布的科技术语。

历史名词是历史上曾出现的事件及事物的名称，例如“禅让”，传说古代实行举荐贤能之人为首领继承人的一种制度，据文献记献：有尧举舜、舜举禹、禹先举皋陶、皋陶死禹又举益等历史故事。

目录

名词解释

NP(Nondeterministic Polynomially，非确定性多项式)类问题是指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。NP类问题数量很大，如完全子图问题、图着色问题、旅行商(TSP)问题等。在P和NP问题中，P的难度最低，NP由于只对验证答案的时间作了限定，从而有可能包含某些无法在多项式时间内找到答案的问题，即NP是比P更困难的问题。

基本介绍

在计算机领域，一般可以将问题分为可解问题和不可解问题。不可解问题也可以分为两类：一类如停机问题，的确无解；另一类虽然有解，但时间复杂度很高。可解问题也分为多项式问题(Polynomial Problem，P问题)和非确定性多项式问题(NondeterministicPolynomial Problem，NP问题)。

P问题

P问题是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。

确定一个问题是否是多项式问题，在计算机科学中非常重要。已经证明，多项式问题是可解问题，因为除了P问题之外的问题，其时间复杂度都很高，即求解需要大量时间。

理论上有解但其时间复杂度巨大的问题，科学家将其称为难解型问题。对计算机来说，这类问题是不可解的。因此，P问题成了区别问题是否可以被计算机求解的一个重要标志。

NP问题

NP问题是指可以在多项式时间内被非确定机解决的问题。通常它们的时间复杂度都是指数变量，如

等。

这里有一个著名的问题一千禧难题之首。是说P问题是否等于NP问题，也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。这表明用NP问题寻找多项式时间表示的算法很困难，或许最后的结论是NP问题根本就不是P问题。

P=NP?问题

目前已经证明所有P问题都是NP问题，那么反之P—NP吗?这就是所谓的“NP问题”。目前P与NP是否等价是一个既没有证实也没有证伪的问题。但是大部分科学家猜想：找一个问题的解很困难，但验证一个解很容易(证比解易)，用公式表示就是P≠NP。问题较难求解(P)但容易验证(NP)，这与我们的日常生活经验是相符的。

【例1】对方程

求解很难，但是验证

很容易。

假设证明了P=NP，那么依据计算复杂性的密码技术就会没有前途，因为答案很容易得到验证的问题也同样可以轻松求解，这将对计算机安全构成巨大威胁。因为目前的加密技术是将一个整数分解为几个因数的乘积，正是因数分解过程烦琐，才保证了信息的安全。

NPC(NP Complete，NP完全)问题

计算机科学家将NP问题中最困难的称为NPC问题。NPC问题有一个令人惊讶的性质，即如果一个NPC问题存在多项式时间算法，那么所有NP问题都可以在多项式时间内求解，即P=NP成立。这是因为每一个NPC问题都可以在多项式时间内转化成任何一个NP问题。只要任意一个NPC问题找到了一个多项式算法，那么所有NP问题都能用这个算法解决，也就解决了NP=P问题。但是给NPC找一个多项式算法太不可想象了，而且也从未成功，因此科学家认为，正是NPC问题的存在，使得人们相信P=NP。

NPC问题目前没有多项式算法，只能用穷举法逐个检验，最终得到答案。但是穷举法的计算时间随问题的复杂程度呈指数增长，很快问题就会变得不可计算了。

围棋或象棋的博弈问题、国际象棋的n皇后问题、密码学中的大素数分解问题等，都属于NPC类问题。

解决NP问题的思路

解决NP问题的一种思路是减少指数的值，这可以节省大量的时间。另一种思路是降低对NP问题的最优化解，使用它的近似解。这方面的研究不仅包括如何得到近似解，也包括解的近似度和局限性，是NP问题的重要研究领域。