PNP问题

2024年4月8日发(作者：无锡统计高中数学试卷)

P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被

“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖

难题中收录。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克

(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题,即是否两

个复杂度类P和NP是恒等的（P=NP?）。

P 和NP

复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决

的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定

问题组成，或者等效的说，那些解可 以在非确定型图灵机上在多项式时间内找

出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的:

P和NP相等吗?

在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯

定的，22个不确定，而8个相信该问题可能和现在所接受的公理独 立，所以不

可能证明或证否。对于正确的解答，有一个$1,000,000美元的奖励。

NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被

描述为那些在NP中最不像在P中的。(确切定义细节请参看NP-完全)理论计算

机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不

交。

假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.

简单来说，P = NP问题问道：如果是/不是问题的正面答案可以很快

验证

，其答

案是否也可以很快

计 算

？这里有一个给你找点这个问题的感觉的例子。给定一

个大数

Y

,我们可以问

Y

是否是复合数。例如，我们可能问53308290611是否有

非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另 一个方面

讲，如果有人声称答案是\"对，因为224737可以整除53308290611\",则我们可以

很快用一个除法来验证。验证一个数是除数比首先找出 除数来简单得多。用于

验证一个正面答案所需的信息也称为

证书

。所以我们的结论是，给定 正确的证

书，问题的正面答案可以很快的(也就是，在多项式时间内)验证，而这就是这个

问题属于NP的原因。虽然这个特定的问题，最近被证明 为也在P类中(参看下

面的关于\"质数在P中\"的参考),这一点也不明显，而且有很多类似的问题相信不

属于类P。

限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问题

(是否FP = FNP)是等价的。

形式化定义

更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问

题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）

能够在最多

n

k

步 内对一个串长度为

n

的输入给出正确答案，其中

k

是某个不依

赖于输入串的常数，则我们称该问题可以在

多项式时间

内 解决，并且将它置入

类P。直观的讲，我们将P中的问题视为可以较快解决的问题。

现在假设有一个算法A(

w

,

C

)取两个参数，一个串

w

，也就是我们的决定问题的输

入串，而另一个串

C

是 “建议证明”，并且使得A在最多

n

k

步之内产生“是/

否”答案（其中

n

是

w

的 长度而

k

不依赖于

w

）。进一步假设

w

是一个答案为“是”的例子，当且仅当，存在

C

使得A(

w

,

C

)返回“是”。

则我们称这个问题可以在

非决定性多项式时间

内解决，且将它放入NP类。我们

把算法A作为一个所建议的证明的检验器，它 运行足够快。（注意缩写NP代表

“Non-deterministic（非确定性）Polynomial（多 项式）”而

不是

代表

“Non-Polynomial（非多项式）。）

NP完全

要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP

类中“最难” 的问题，也就是说它们是最可能不属于P类的。这是因为

任何

NP

中的问题可以在多项式时间内变换成为任何特定NP完 全问题的一个特例。例如，

旅行商问题的判定问题版本是NP完全的。所以NP中的

任何

问题的

任 何

特例可

以在多项式时间内机械地转换成旅行商问题的一个特例。 所以若旅行商问题被

证明为在P内，则P = NP！ 旅行商问题是很多这样的NP完全的问题之一。若

任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问

题被证明为NP完全，但没有一个有已知快速的算法。

更难的问题