P/NP问题

P/NP问题（英語：P versus NP problem）是理论计算机科学中一个核心的未解问题。通俗而言，它探讨的是：如果一个问题的答案能够被快速验证，那么这个问题本身是否也能被快速求解？

具体而言，这里的“快速”指的是存在一种算法，可以在与输入规模呈多项式时间的关系内计算出结果（这与耗时极长的指数时间等概念相对）。换言之，完成任务所需的时间上限是输入规模的多项式函数。那些能在多项式时间内被算法解决的判定问题类别，被称为“P”或“P类问题”。相反，对于某些问题，目前人类还没有找到快速求解的方法，但如果有人提供一个候选解，我们却能快速验证它是否正确。这类解能在多项式时间内被验证的问题类别，被称为“NP”（即“非确定性多项式时间”）。^{[Note 1][1]}

P/NP问题的答案将直接决定：那些解法容易被验证的问题，是否也必然容易被求解。如果结果如目前学术界普遍猜想的那样（即 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$），那就意味着NP类别中存在一些问题，它们的解极易验证，但想要直接计算出解却极其困难（无法在多项式时间内求解）。

该猜想被公认为计算机科学领域最重要的未解之谜。^[2] 它不仅是计算理论的基石，而且无论其最终证明结果如何，都必将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学以及经济学等众多领域产生深远影响。^[3] 该问题也是克雷数学研究所评选出的七大千禧年大奖难题之一，首个提供严谨证明的人将获得100万美元的奖金。

以一个判定问题为例：给定一个 ${\displaystyle n^{2}\times n^{2}}$ 的不完整数独棋盘，是否存在至少一种合法的填法，使得每行、每列以及每个 ${\displaystyle n\times n}$ 的宫格都恰好包含从 1 到 ${\displaystyle n^{2}}$ 的所有整数？如果有人提供了一个填好的候选解，我们能相对快速地验证这个广义数独的答案是否正确。然而，目前学术界尚不清楚，是否存在一种能够在多项式时间内运行的算法，可以直接推算盘面并准确回答“是否有解”。因此，广义数独问题属于NP类（解的正确性可被快速验证），但它究竟是否属于P类（能否被快速推算求解），目前仍是未知数。（这里讨论广义数独很有必要，因为对于我们日常见到的标准 9×9 数独，其可能的组合只有有限种，计算机完全能在短时间内通过查表找到答案，因此固定规模下的数独实际上属于P类。）

P/NP问题的严格定义最早由斯蒂芬·库克在1971年的开创性论文《定理证明程序的复杂性》（英語：The complexity of theorem proving procedures）中提出，^[4] 数学家列昂尼德·列文也在1973年独立提出了完全相同的定理。^[5]

尽管P/NP问题直到1971年才被赋予正式的学术定义，但人们对潜藏其背后的底层逻辑早有察觉。1955年，著名数学家约翰·纳什在写给美国国家安全局的一封信中推测，破解一个足够复杂的密码所需的时间，将随着密钥长度的增加呈指数级增长。^[6] 如果纳什的推测成立（尽管他本人亦持怀疑态度），这就等同于如今所说的 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 猜想，因为尝试性的密钥是能够在多项式时间内被验证的。1956年，库尔特·哥德尔在写给约翰·冯·诺伊曼的一封著名信件中，也询问了定理证明过程（如今已知为反NP完全问题）是否能在二次时间或线性时间内解决。^[7] 他假定，如果能在多项式时间内解决，那么数学证明的过程就能被自动化。

复杂性类 P与NP之间的关系，是计算复杂性理论（计算理论的一个重要分支）的核心研究对象。该理论主要研究在计算过程中，解决给定问题需要耗费多少资源。最关注的两种资源是“时间”（计算步骤数）和“空间”（内存消耗量）。

为了精确进行这种分析，我们需要引入理论模型来计算机器耗费的时间。通常，这些模型会假定计算机是确定性计算的（即给定当前状态和输入，计算机只能采取唯一的一种操作），并且是顺序的（只能逐条执行操作）。

在这一理论框架下，P类包含的所有判定问题都可以由一台确定性顺序机器在输入规模的多项式时间内解答；而NP类则包含所有如果在给定正确提示的情况下，能够于多项式时间内顺利验证肯定解的判定问题。这等价于说，NP类问题是能够在一台非确定性图灵机上于多项式时间内找到解的问题。^[8] 显然，P类是包含于NP类之中的（${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}}$）。可以说，理论计算机科学界最大的未解之谜，就是这两个复杂性类别之间的关系：

P等于NP吗？

自2001年起，学者威廉·加萨奇针对 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 及其相关议题，向计算机科学界的研究人员进行了三次问卷调查。^[9][10][11] 认为 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 的受访者比例在2001年占61%，^{[Note 2]} 到了2011年上升至83%，而在2018年则达到了88%（这三次调查分别收到了100份、151份和124份回复）。^[11] 当把统计范围仅限定为领域内的顶级专家时，2018年高达99%的受访者认为 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$。^[11] 当然，民意调查并不能在数学上证明 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 是否成立；正如加萨奇本人所言：“这并没有让我们在解决问题上迈进哪怕一步，也没有告诉我们它何时会被解决。这仅仅是一份关于我们这个时代主观意见的客观报告。”^[9]

“NP完全”（NP-complete）概念在探索 P/NP 问题时发挥了关键作用。一个问题被称为NP完全问题，意味着所有其他NP问题都能在多项式时间内归约（转化为）该问题，且它自身的解也能在多项式时间内被验证。通俗来讲，NP完全问题是所有NP问题中最困难的一类，它至少与任何其他NP问题一样具有挑战性。

而NP困难问题是指那些难度至少与NP问题相当的难题；即，所有NP问题都能够在多项式时间内归约到它们。需要注意的是，NP困难问题自身不一定属于NP；换言之，它们的解不一定能在多项式时间内被验证。

举个例子，由著名的库克-列文定理可知，布尔可满足性问题（SAT）是一个典型的NP完全问题。因此，NP类别中任何问题的任何实例，都可以在多项式时间内机械地转化为布尔可满足性问题。只要能证明任何一个NP完全问题属于P类（即找到了多项式时间的解法），就能直接推导出 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$。然而，许多重要的现实问题已被证明是NP完全的，且至今尚未找到能快速求解它们的算法。

仅看定义，去相信“NP完全问题真的存在”似乎有些反直觉；但实际上，我们可以轻易构造出一个微不足道的NP完全问题：给定一台保证在多项式时间内停机的图灵机 ${\displaystyle M}$，是否存在一个多项式大小的输入能让 ${\displaystyle M}$ 接受？^[12] 它属于NP类，因为（给定输入后）我们只需运行一遍 ${\displaystyle M}$，就能轻松检查 ${\displaystyle M}$ 是否接受；同时它也是NP完全的，因为任何NP问题实例的验证器，都可以编码为一台以“待验证的解”作为输入的多项式时间机器 ${\displaystyle M}$。该实例是否有解，完全等价于是否存在能让 ${\displaystyle M}$ 接受的有效输入。

历史上第一个被证明为自然的NP完全问题正是布尔可满足性问题（SAT）。如前所述，这也是库克-列文定理的意义所在；其证明过程包含了大量与图灵机底层机制及NP严格定义相关的技术细节。然而，在SAT问题被确认为NP完全之后，学者们利用归约证明这种更为简便的方法，通过逐步推导证明了许多其他问题同样是NP完全的，其中就包括前文提到的数独游戏。在这种归约逻辑下：如果在多项式时间内能解出广义数独，那么这套解法就能被直接套用来在多项式时间内完成拉丁方阵。^[13] 拉丁方阵的高效解法又能进一步为将三分图划分为三角形的问题提供解法，^[14] 这又能解决一种被称为3-SAT的特殊SAT问题，^[15] 并最终解决一般化的布尔可满足性问题。综上所述，广义数独的多项式时间解法通过一系列归约，能直接引出SAT问题的多项式时间解法，而SAT的解法又能用来解决所有其他NP问题。正是借助这种转换机制，一大批表面上看似毫无关联的问题被相互串联了起来。

尽管学术界至今无法确定P是否等于NP，但在P类之外，确实存在更为困难的问题。正如P类是根据多项式运行时间界定的一样，EXPTIME类包含所有运行时间呈指数级增长的判定问题。换言之，EXPTIME中的任何问题都可以在由确定性图灵机耗费大O符号 ${\displaystyle O(2^{p(n)})}$ 的时间内解决，其中 ${\displaystyle p(n)}$ 是 ${\displaystyle n}$ 的多项式函数。如果一个判定问题本身属于EXPTIME，并且EXPTIME中的所有问题都能通过多项式时间归约转化为该问题，那么它被称为EXPTIME完全。目前已证实存在许多EXPTIME完全问题。因为数学上已经证明了 ${\displaystyle {\mathsf {P}}\neq {\mathsf {EXPTIME}}}$，这些问题被明确排除在P类之外，求解它们必然需要耗费超过多项式时间的资源。事实上，时间层次定理已经严格证明，这类问题绝不可能在远低于指数级的时间内得到解决。现实中的例子包括：在 ${\displaystyle N\times N}$ 的棋盘上推演出完美的国际象棋必胜策略^[16]，以及其他各类复杂棋盘游戏的类似问题。^[17]

去判定普莱斯伯格算术中语句的真伪，需要耗费更长的时间。费雪和拉宾在1974年给出了严谨证明：^[18] 任何用于判断长度为 ${\displaystyle n}$ 的普莱斯伯格语句真伪的算法，其运行时间都至少会达到 ${\displaystyle 2^{2^{cn}}}$（其中 ${\displaystyle c}$ 为某个常数）。因此，这类问题被证明需要超过指数级的运行时间。而比这还要艰难的，则是那些逻辑上无法被算法解答的不可判定问题，例如著名的停机问题。它们无法由任何通用算法彻底解决；也就是说，对于任何特定算法，必定存在至少一个输入使其无法输出正确答案：它要么输出错误结果，要么陷入死循环永远无法停止。

除了讨论“是否有解”的判定问题，复杂性理论还关注其他计算类型。其中一类由计数问题组成，被称为#P类别：既然NP探讨的是“问题是否有解？”，那么相对应的#P探讨的则是“问题究竟有多少个解？”。显然，如果算出的解数大于零，就立刻表明至少存在一个解，因此#P问题的难度门槛绝对不低于其对应的NP问题。令人惊讶的是，某些看似极难的#P问题，其对应的判定问题却相对容易（例如可以在线性时间内求解的P问题）。^[19] 对于这类问题，判断“是否有解”相对简单，但确切算出“有多少个解”却极其困难。这类问题大部分属于#P完全，也就是#P类别中的最高难度问题，只要找到针对其中任意一个难题的多项式时间解法，就能直接为所有其他#P问题提供多项式解法。

1975年，学者理查德·拉德纳提出了一个重要证明：如果 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$，那么在NP的大框架内，必定存在既不属于P、也不属于NP完全的问题。^[20] 这类问题被称为“NP中介问题”。包括图同构问题、离散对数问题以及整数分解问题等，都被视为NP中介问题的典型代表。它们是极少数尚无定论、难以直接判定其究竟属于P还是NP完全的NP难题。

图同构问题旨在判定两个有限的图之间是否存在图同构关系。在复杂性理论界，图同构问题究竟归属于P、NP完全还是NP中介，一直是一个备受瞩目的未解悬案。虽然最终答案仍未确定，但主流观点普遍认为该问题至少不应当是NP完全的。^[21] 如果图同构真的是NP完全问题，那么根据理论推导，整个多项式时间层次体系将会坍缩到它的第二层。^[22] 由于学术界普遍认为多项式层次绝不会坍缩到有限层，因此更倾向于认为图同构不是NP完全问题。由拉兹洛·巴拜提出的求解该问题的目前已知最佳算法，能够在准多项式时间内运行完毕。^[23]

整数分解问题旨在求出一个给定整数的精准素数分解。将其转化为判定问题即为：判断输入的数字是否具有小于某个特定值 ${\displaystyle k}$ 的素因子。时至今日，人类尚未找到任何已知的高效整数分解算法，而正是基于这种难以破解的数学特性，构筑了诸如RSA算法等现代密码系统的安全基石。整数分解问题同时归属于NP与co-NP（甚至属于更为特殊的UP和co-UP^[24]）。如果能证明该问题是NP完全的，那么多项式时间层次将彻底坍缩到第一层（即 ${\displaystyle {\mathsf {NP}}={\mathsf {co-NP}}}$）。目前已知针对大整数分解最高效的经典算法是普通数域筛选法，它在分解一个长达 ${\displaystyle n}$ 位的整数时，所耗费的期望时间为：

${\displaystyle O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)}$

在量子计算领域，针对该问题的最佳已知量子算法是极具革命性的秀尔算法，它能够在多项式时间内运行，尽管这一壮举尚未完全明确该问题在非量子复杂性理论中具体所处的类别坐标。

前文的所有探讨都建立在一个普遍的假设之上：即认为P类代表“计算简单”，而“不在P中”代表“计算困难”。在复杂性理论中，这一假设被称为“科巴姆论题”。尽管这是领域内的共识，但在现实应用中，它同样存在一些不容忽视的局限性。

首先，从工程实践的角度来看，这个理论可能会脱节。一个在理论上被证明属于多项式时间的算法，可能携带着巨大的常数因子或庞大的指数项，导致它在实际应用中难以运行。例如，判定一个图 ${\displaystyle G}$ 是否包含特定的图 ${\displaystyle H}$ 作为其图子式，在理论上能够以 ${\displaystyle O(n^{2})}$ 的运行时间解决，^[26] 其中的 ${\displaystyle n}$ 代表图 ${\displaystyle G}$ 中的顶点总数。然而，大O符号在这个 ${\displaystyle O(n^{2})}$ 背后隐藏了一个极大的常数，该常数对 ${\displaystyle H}$ 呈现多重指数级的依赖。这个常数甚至比 ${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$ （采用高德纳箭号表示法）还要巨大，其中的 ${\displaystyle h}$ 是 ${\displaystyle H}$ 中的顶点数。^[27]

另一方面，就算某个问题被定性为NP完全，甚至即便 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 成立，在实践中依然可能有应对该难题的有效手段。许多典型的NP完全问题，例如背包问题、旅行推销员问题以及布尔可满足性问题等，目前都已拥有非常成熟的现成算法，它们能够以令人满意的速度，在合理时间内找到许多现实世界复杂实例的最优解。这些算法在经验测试中展现出的平均情况复杂性（耗时与问题规模的对比）往往相对较低。一个例子是线性规划中的单纯形法，它在现实工业应用中表现得非常优异；尽管在极端的理论最坏情况下，它具有指数级的高时间复杂度，但它在绝大部分日常运算中的表现，并不逊色于目前任何已知的多项式时间算法。^[28]

此外，P与NP的定义完全根植于传统的经典图灵机模型。如果我们把目光投向不符合该模型的其他前沿计算类型，例如量子计算和随机算法，整个复杂性理论体系可能会呈现出完全不同的风貌。

库克在《P与NP问题》（The P Versus NP Problem）一文中，将该问题精炼地表述为：“P = NP 吗？”^[29] 根据历次民意调查结果，^[9][30] 绝大多数计算机科学家倾向于认为 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$。支撑这一主流信念的一个重要理由是：在大量学者对这些问题进行了长达数十年的深入研究之后，时至今日，依然没有任何一个人能够为3000多个已知的重要NP完全问题（参见NP完全问题列表）中的任何一个找到多项式时间算法。事实上，早在NP完全性概念被正式提出之前，人们就已经在寻找这些算法了（例如最先被发现的卡普的21个NP完全问题，在它们被证明为NP完全时，就已经全是当时困扰学界已久的难题）。此外，如果未来某一天得出 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 的结论，将导致许多目前在学界被认为极度不成立的结论随之成立，例如 ${\displaystyle {\mathsf {NP}}={\mathsf {co-NP}}}$ 以及 ${\displaystyle {\mathsf {P}}={\mathsf {PH}}}$。

从人类直觉的层面来看，有一种颇具说服力的观点认为：世界上确实存在着那些“解答困难，但验证容易”的问题，这契合我们在现实生活中的真实经验。^[31]

如果 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，那么这个世界的运转逻辑将与我们往常假设的截然不同。所谓的“创造性飞跃”将不再具有任何特殊价值，而在费尽心思解决一个难题与答案被找到后一眼识别出它之间，也不再存在根本的智力鸿沟。

——斯科特·阿伦森，得克萨斯大学奥斯汀分校

另一方面，也有少数研究人员提出不同观点，认为绝对认定 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 可能缺乏严谨的求证精神，研究人员同样应当探索 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 的可能性。例如，在2002年就有人发表了如下声明：^[9]

支持 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 的最主要论点，无非是在算法穷举搜索领域完全缺乏任何根本性的进展。但在我看来，这是一个不够充分的论点。算法的探索空间是极其浩瀚的，而我们人类目前仅仅处于探索的起步阶段。[...] 费马大定理最终的解决历程也生动地向我们表明，某些看似简单的问题，往往只能通过深奥的理论才能得以破解。

——摩西·瓦尔迪，莱斯大学

过度坚持一种未经证实的猜测，不是规划严谨学术研究的好指引。我们理应对每一个未解之谜尝试从正反两个方向同时入手。盲目的偏见已经导致了历史上许多杰出的数学家在解决著名问题时遭遇挫折——即便他们有时已经掌握了推导所需的所有工具，但仅仅因为问题的真实答案与他们的预期背道而驰，最终依然未能成功。

——阿尼尔·尼洛德，康奈尔大学

如果在P和NP的严格定义中，我们用“多带图灵机上的线性时间”替换“多项式时间”这一条件，就会得到DLIN和NLIN这两个全新的复杂性类别。 目前在数学上已经明确证实^[32]：DLIN ≠ NLIN。

这个问题之所以能吸引全球学者的关注，核心原因之一就在于它可能带来的巨大影响。无论最终朝着哪个方向被解决，都将带来理论计算机科学的重大飞跃，甚至可能改变现实社会的应用版图。

如果真的证明了 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，这将引发巨大的实际影响——前提是该证明能够顺势牵引出一种求解某些高价值NP问题的高效算法。由于各类NP完全问题在现代科学的诸多领域都是基础性问题，这一证明带来的正负面潜在影响将是难以估量的。

然而，同样可能发生的情况是，即便给出了证明，它也无法为NP完全问题带来任何在现实中可运行的实用算法。因为P/NP问题的原始公式设定并没有要求作为运行时间上限的那个“多项式”必须很小，或者必须被明确计算出来。一个纯粹的非构造性证明可能仅仅在数学逻辑上宣告了“存在这样一个解”，但既不提供获取它的算法代码，也无法给出一个具体的算力消耗界限。退一步说，即使该证明是严谨的构造性证明，清晰展现了多项式界限和算法执行细节，但如果该多项式的阶数极大（例如需要 ${\displaystyle O(n^{100})}$ 的时间），那么该算法在当前的物理世界中依然缺乏实际应用价值。在这种情况下，这个证明最初将仅仅限于理论探讨；不过，得知多项式时间解法在理论上可行，无疑会极大激励研究人员去寻找更好的实际实现路径。

一旦拿出了极具实用价值的 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 解答，整个现代密码学体系可能面临失效风险，因为该领域的运作根基，恰恰建立在“某些计算问题属于无法在多项式时间内求解的困难问题”这一信念之上。设想一下，如果能为一个像3-SAT这样的NP完全问题找到一种高效解法^{[Note 3]}，那么现存于世的大多数防线将被击穿，这其中包括：

• 现有公开密钥加密算法的主流商业实现，^[33] 这是支撑全球互联网通信和金融交易的安全基础。
• 用于加密通信数据本身的对称密钥加密技术，例如高级加密标准（AES）或传统的三重资料加密演算法（3DES）。^[34]
• 密码散列函数，它是所有区块链加密货币（如著名的比特币）运转的基础，也被广泛用于验证全球软件更新包的真实性与防篡改。对于这些应用而言，逆向寻找一个能散列出给定特征值的原始数据，必须被设计得极其困难。可一旦 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，通过向SAT问题进行简单的归约，现有的加密体系就有可能在多项式时间内被破解。^[35]

为了应对危机，全球的基础网络系统必须被迫进行全面升级，或者切换为那些完全不依赖 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 假设的信息论安全方案。

当然，将目前在数学上难以处理的问题变得易于处理，也将为社会带来科技红利。例如，运筹学中的大量核心优化问题都是NP完全的，如负责调度的各类整数规划，以及旅行推销员问题。一旦为这些问题配备了高效解法，将极大降低运输与制造成本。许多其他重大的科学问题，比如医学界蛋白质结构预测中的某些关键折叠问题，同样是NP完全的；^[36] 解决它们将促进新药研发和生物技术的发展。

与高效求解NP难题带来的影响相比，上述行业变化或许只是一部分。哥德尔在早期关于计算复杂性的思考中就曾指出：如果世上真的存在一种能够解决任何逻辑问题的机械方法，那将极大地改变数学家的工作方式：^[37][38]

如果真的存在一台运算满足 ${\displaystyle \varphi (n)\sim k\cdot n}$（甚至哪怕满足 ${\displaystyle \sim k\cdot n^{2}}$）的机器，那必将引发极其重大的后果。这表明，尽管判定问题具有不可判定性，但数学家在回答“是或否”这类定理真伪问题上的劳作，都可以被机器取代。毕竟，我们只需要把自然数 ${\displaystyle n}$ 设置得足够大，如果连这台机器都无法给出结果，那么人类再花更长时间去思考这个问题，也就没有实际意义了。

同样地，斯蒂芬·库克也描绘了这样一幅图景：^[29]

... 它将赋予计算机极大的能力，去自动搜寻任何存在合理长度证明的定理的形式化证明。因为形式化的证明在多项式时间内是极容易被机器识别和验证的。这必将彻底改写数学体系的形态。一旦机器拥有了这种能力，所有悬而未决的克雷数学研究所千禧年大奖难题都可能被迅速解决。

几千年来，研究型数学家致力于证明各种晦涩的定理。有些证明在问题提出后，往往需要耗费数十年的时间才能被攻克——例如，费马大定理就花了三百多年的时间才得以彻底证明。如果真的存在一种终极算法，只要某个定理存在“合理”长度的证明，就必然能轻易地找到它，那么这方面的学术研究将发生根本性改变。

计算机科学家高德纳曾表示，他倾向于相信 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，但他对这一潜在证明可能带来的实际影响抱保守态度：^[39]

[...] 假设存在一个数字 ${\displaystyle M}$，它极其庞大——比如 ${\displaystyle 10\uparrow \uparrow \uparrow \uparrow 3}$——那么在这个范围内，必然存在着海量的潜在算法，它们可以对 ${\displaystyle n}$ 个给定的比特执行 ${\displaystyle n^{M}}$ 次运算。从概率学上讲，你很难相信在如此海量的潜在算法中，完全不存在任何有效的算法。 然而，我不认为即使有人证明了 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，能给实际的程序编写带来立竿见影的帮助。因为这种证明，几乎肯定是不提供具体构造方法的非构造性证明。

如果最终被证明出的是 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$，虽然它否定了通过单一算法解决所有难题的设想，缺乏 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 证明所能带来的现实计算红利，但它依然代表了计算复杂性理论认知上的进步，并为未来的研究指明方向。它将清楚地告示人们：许多研究了半个世纪的常见难题，根本不可能存在完美的高效通用解法。这能让研究人员及时调整方向，把精力转移到寻找局部最优解、近似解或解决其他问题上。事实上，正是由于当今学术界普遍认为 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$，这种科研重心的转移早已在各行各业发生。^[40]

然而，${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 这一结论，依然无法解答关于NP内部那些棘手问题的平均情况复杂性疑虑。举个例子：SAT问题在遇到极端恶劣的最坏情况时，确实可能需要耗费指数级的时间来破解；但在真实工程中，如果我们随机抽取一些SAT的常规实例，它们往往能够被高效求解。学者罗素·因帕利亚佐曾构建过一个思想实验，描述了由“平均情况复杂性问题”不同可能解答所催生出的五个假设世界。^[41] 这些世界从理想的“算法乌托邦”（Algorithmica，在这个世界里 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，任何实例都能被轻松求解），一路滑向复杂的“密码狂热世界”（Cryptomania，在这个世界里 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$，并且人为制造困难实例相对容易）。在这两极之间，还存在三种过渡性世界，映射了计算难度的各种情况。在他的论文中，那个虽然 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 成立，但几乎所有NP问题在平均情况下都会变得容易处理的世界，被命名为“启发式世界”（Heuristica）。2009年，在普林斯顿大学的一场研讨会上，学者们专门围绕这五个世界的理论现状展开了探讨。^[42]

尽管 P/NP 问题自身带有巨额赏金，并且吸引了全球众多学者的持续研究，但它至今依然悬而未决。然而，全人类为了解决这个问题所付出的巨大努力，催生了一大批数学分析新技术的诞生。特别需要强调的是，与 P/NP 问题相关的一些重要科研成果，恰恰证明了：人类目前所掌握的任何已知论证技术，都不足以回答这个问题。这宣告了想要解决这个问题，就必须开辟全新的技术路径。

作为该问题难度之高的另一佐证，可以审视目前计算复杂性理论中几乎所有已知的高级证明技术。它们全都被归入以下几种分类，且无一例外，全都在证明 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 时遭遇壁垒：

分类	定义
相对化证明	在理论模型中构建这样一个特定的世界：允许每一个算法向某个被称为预言机的子程序发起询问（它能在常数时间内立刻解答一组固定范围内的难题），并且该预言机的运行时间不计入算法自身的运行时间内。大多数传统的证明手法（尤其是经典的推导证明），在这个设定中都能顺畅应用，无论预言机背后执行什么操作。这类高度依赖该设定的证明手法被称为相对化的。1975年，贝克（Baker）、吉尔（Gill）和罗伯特·索洛维联手证明了一个重要结论：对于某些特定的预言机，存在 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 的情况；而换用另一些预言机，结果又变成 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$。[43] 由于相对化证明体系只能证明那些对所有可能预言机都绝对成立的普适陈述，这就注定了这种受限的技术路径无法解决 P/NP 问题。
自然证明	1993年，学者亚历山大·拉兹波罗夫和斯蒂芬·鲁迪奇为电路复杂性下界定义了一大类通用的证明技术框架，将其命名为自然证明。[44] 当时，所有已知的电路下界证明无一例外都是基于这种路线的，而破解电路复杂性一直被学术界视为有望解决 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 的最可能突破口。然而，拉兹波罗夫和鲁迪奇随后证明：只要存在哪怕一种单向函数，那么对于这种“自然证明”方法而言，P和NP就是难以区分的。虽然至今单向函数在数学上的存在性尚未被完全证实，但绝大多数数学家都相信它们存在，并且从逻辑上讲，想要证明单向函数存在，本身就是一个比证明 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 更强有力的断言。因此，指望单凭传统的自然证明去解决 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 是极不现实的。
代数化证明	在得出上述结论后，新的非相对化证明技术出现，并被成功用于跨界证明 IP = PSPACE 这一重要定理。然而到了2008年，学者斯科特·阿伦森和阿维·威格森证明了：在 IP = PSPACE 证明中使用的核心技术（被称为算术化技术），在面对 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 时同样无能为力。[45] 算术化技术的精髓在于能够把复杂的算法运算巧妙转化为纯粹的代数与算术符号。在 IP = PSPACE 的证明中，他们将算法的黑盒和底层布尔电路转化为了代数问题。[45] 正如前文所述，残酷的事实表明，这种代数化的方法在直面 P/NP 及其他深度的时间复杂度难题上，同样受到了限制。

上述理论壁垒从侧面说明了为什么“NP完全问题”如此具有价值：假使某位学者能够为任意一个NP完全问题找到多项式时间算法，这便能以一种无视上述理论壁垒阻碍的突破性方式，一劳永逸地解决 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 问题。

正是这些看似难以逾越的理论壁垒，促使一部分计算机科学家提出一个大胆猜想：P/NP问题本质上可能完全独立于诸如ZFC这样的标准数学公理系统。如果这一结论最终被证实，意味着两种可能：要么 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ 成立，但这在ZFC系统中无法被证明；要么 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，但即便找到了高效算法，在ZFC系统内也永远无法给出严谨的数学证明去背书这些算法的正确性。^[46] 值得注意的是，如果退让一步，引入远比扩展整数算术的皮亚诺公理弱的假设，该问题仍然具有不可判定性，那么根据逆向推导，所有庞大的NP问题群体都必然会存在某种接近多项式时间的极其高效的算法。^[47] 既然绝大多数理论学家都相信许多NP问题不存在如此高效的算法，那么妄图利用现有技术去证明“独立性”，同样是一条走不通的路。这表明，想要用人类目前掌握的技术证明该问题独立于PA或ZFC系统，其难度与证明“所有NP问题都存在高效算法”一样是不切实际的。

得益于在描述复杂性领域的突破，P/NP问题能够被重新表述为对某些特定形式的逻辑陈述类别的探讨。

考虑所有带有包含线性序关系在内的某个固定签名的有限结构的语言集合。归属于P类的语言，实际上都可以通过在传统的一阶逻辑基础上，加上特定的最小不动点组合子来进行表达。只要这个签名系统中，除了序关系外还包含至少一个谓词或函数，使得计算机在存储此类有限结构时所占用的空间，受限于该结构中元素数量的多项式规模，这套理论就刻画了P类的特征。

NP类也能被类似地映射出来。它实质上可以用存在性二阶逻辑（这里特指一种受限的、排除了针对关系、函数及子集的全称量化的二阶逻辑变体）来表达的语言集合。而那些属于多项式时间层次PH的语言，则对应于完整的二阶逻辑。经过这一理论转换，“P是否仅仅是NP的一个真子集”这一问题，就可以表述为：“针对具有非平凡签名的有限线性有序结构，存在性二阶逻辑是否具备描述‘一阶逻辑搭配最小不动点组合子’所无法触及的语言的能力？”。^[48] 甚至前面这个描述中的“存在性”这三个字都可以被省略，因为当且仅当 ${\displaystyle {\mathsf {P}}={\mathsf {PH}}}$ 成立时，${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 才成立。

目前没有任何已知针对NP完全问题的算法，能够在现实环境的多项式时间内运行完毕。然而，对于某些极度难缠的NP完全问题，理论上确实存在已知算法，且如果 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 成立，该算法在处理肯定的输入实例时将会快速运行（尽管该算法中包含的常数项极其庞大，导致它在任何物理计算机上都缺乏实用价值）。由于这些算法在处理否定的实例时，运行耗时依然会大幅突破多项式时间限制，因此它们仍不符合“绝对多项式时间”的定义。下面这个由学者列昂尼德·列文提出的特殊算法，正是这样一个极端的例子。它能够接受NP完全语言子集和问题（SUBSET-SUM）。当且仅当 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 成为现实时，该算法在处理属于SUBSET-SUM的输入时，才会在多项式时间内运行完毕：

 // 接受NP完全语言SUBSET-SUM的伪代码算法。
 //
 // 当且仅当 P = NP 成立时，这是一个多项式时间算法。
 //
 // 这里“多项式时间”的真实含义是：当问题的答案为“是”时，它会在多项式时间内输出“是”；
 // 而当答案为“否”时，它会陷入死循环，永远运行下去。
 //
 // 输入：S = 一个有限的整数集合
 // 输出：如果 S 中存在任何一个子集的元素之和恰好为 0，则输出“是”。
 // 否则程序将永远运行，不产生任何输出。
 // 注意：“程序 M”是通过暴力枚举得来的：
 // 将整数 M 直接转换为二进制，并将其强行视为一段可执行程序。
 // 理论上所有可能存在的程序都能以此方式生成，尽管大部分
 // 在第一步就会因为语法错误而立刻崩溃。
 FOR K = 1...∞
   FOR M = 1...K
     以 S 为输入，强行运行“程序 M” K 个计算步
     IF 该程序输出一个由不同整数组成的列表
       AND 这些整数全都毫无遗漏地包含在原集合 S 中
       AND 这些整数的累加之和恰好为 0
     THEN
       OUTPUT "是" 并触发 HALT（停机指令）

这绝对是一个唯有当 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 降临时，才能够在多项式时间内成功接受NP完全语言的特殊算法。在这里对“接受”一词的定义非常宽容：它意味着算法在多项式时间内明确给出“是”的结果，但当答案为“否”时，允许其无休止地运行（这种算法在理论上也被称作半算法）。

即使 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，该算法也因为其暴力的穷举逻辑而显得极度不切实际。试想一下，如果能够在一套正常逻辑框架下，在多项式时间内解决SUBSET-SUM问题的最短且最优程序代码长度仅为 ${\displaystyle b}$ 个比特，那么上述算法在盲目尝试得出正确答案之前，至少需要尝试执行高达 ${\displaystyle 2^{b}-1}$ 个无效程序。

在计算理论的严谨框架下，一个标准的判定问题指的是这样一个逻辑设定：它接收由底层字母表 Σ 构建出的特定字符串 ${\displaystyle w}$ 作为唯一输入，并输出“是”或“否”。如果存在一种算法（可以具象化为一台绝对理性的图灵机，或者一段占用必要内存的计算机程序），能够在最多 ${\displaystyle cn^{k}}$ 步的算力消耗内，针对任何长度为 ${\displaystyle n}$ 的输入字符串可靠地产生正确答案（其中 ${\displaystyle k}$ 和 ${\displaystyle c}$ 是两个恒定不变的常数），那么我们在理论上就宣称该问题可以在多项式时间内被解决，并将其归入类别P。用数学语言形式化地表述，P 类就是那些能够被确定性多项式时间图灵机判定的语言集合。即，

${\displaystyle {\mathsf {P}}=\{L:L=L(M){\text{ 对某个确定性多项式时间图灵机 }}M\}}$

其中

${\displaystyle L(M)=\{w\in \Sigma ^{*}:M{\text{ 接受 }}w\}}$

并且，这里所谓的“确定性多项式时间图灵机”，指的是必须满足以下两条规则的确定性图灵机 ${\displaystyle M}$：

1. ${\displaystyle M}$ 在面对所有可能的输入 ${\displaystyle w}$ 时，都必须保证最终停机，并且
2. 必然存在某个自然数 ${\displaystyle k\in N}$，使得 ${\displaystyle T_{M}(n)\in O(n^{k})}$ 成立，这里的 ${\displaystyle O}$ 指代大O符号的正式定义，并且

${\displaystyle T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}}$

${\displaystyle t_{M}(w)=M{\text{ 在处理输入 }}w{\text{ 上直至停机所必须耗费的总步数。}}}$

NP类的定义也可以用极为相似的方式推导，只需引入非确定性概念即可（这是理论界最传统的定义法）。然而，现代学术界更青睐采用证书与验证器概念。形式化地讲，NP类是定义在有限基础字母表上的、并且拥有一个能受控在多项式时间内运行完毕的验证器的语言集合。关于“验证器”的定义如下：

设 ${\displaystyle L}$ 是定义在有限字母表 Σ 上的语言集。

${\displaystyle L\in {\mathsf {NP}}}$ 能够成立的充要条件是：存在一个二元关系 ${\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}}$ 以及一个正整数 ${\displaystyle k}$，满足以下两个条件：

1. 对所有 ${\displaystyle x\in \Sigma ^{*}}$，${\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}$ 使得 ${\displaystyle (x,y)\in R}$ 且 ${\displaystyle |y|\in O(|x|^{k})}$；并且
2. 语言 定义在 ${\displaystyle \Sigma \cup \{\#\}}$ 上的 ${\displaystyle L_{R}=\{x\#y:(x,y)\in R\}}$ 能够被一台确定性图灵机在多项式时间内判定。

能够判定 ${\displaystyle L_{R}}$ 的图灵机，便被称为 ${\displaystyle L}$ 的验证器，而那个能使得 ${\displaystyle (x,y)\in R}$ 逻辑成立的 ${\displaystyle y}$，被称为 ${\displaystyle x}$ 属于 ${\displaystyle L}$ 的成员证书。

并非所有的验证器都必须被限制在多项式时间内。但核心在于：要使得某个语言 ${\displaystyle L}$ 归属 NP 类别，就必须存在至少一个能够在多项式时间内运行完毕的验证器。

设

${\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ 对于整数 }}p,q>1\right\}}$

${\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ 且 }}y{\text{ 整除 }}x\right\}.}$

判断一个特定值 ${\displaystyle x}$ 是否为合数的问题，本质上等价于判断 ${\displaystyle x}$ 是否有资格成为集合 COMPOSITE 的成员。通过验证它是否契合上述定义，学术界可以证明 COMPOSITE ∈ NP。

后来，随着AKS质数测试算法的提出，进一步证明了 COMPOSITE 其实也归属于P类。^[49]

关于NP完全性，学术界有着等价的表述方式。

设 ${\displaystyle L}$ 是一个定义在有限字母表 Σ 上的语言集合。

${\displaystyle L}$ 被称为“NP完全”，当且仅当它满足以下两个条件：

1. ${\displaystyle L\in {\mathsf {NP}}}$；并且
2. 任何其他属于 NP 类别的语言 ${\displaystyle L'}$，都能够在多项式时间内归约至 ${\displaystyle L}$（记作 ${\displaystyle L'\leq _{p}L}$）。这里的 ${\displaystyle L'\leq _{p}L}$ 成立，当且仅当满足以下两条规则：
   1. 存在一个转换函数 ${\displaystyle f}$ : Σ* → Σ* 能够使得对于 Σ* 中的所有输入 ${\displaystyle w}$，都有一个绝对成立的等式：${\displaystyle (w\in L'\Leftrightarrow f(w)\in L)}$；并且
   2. 存在一台拥有多项式时间极限运算能力的图灵机，在接收到任何输入 ${\displaystyle w}$ 时都保证能停机，且输出必须是 ${\displaystyle f(w)}$。

换言之：如果 ${\displaystyle L\in {\mathsf {NP}}}$，并且刚好有另外某个已知的NP完全问题，能够在多项式时间内归约至 ${\displaystyle L}$，那么 ${\displaystyle L}$ 本身便也成为NP完全问题。这也是计算机科学家在证明某个新问题为NP完全时最常用的方法。

尽管P与NP问题被公认为尚未被攻克的悬案，^[50] 但这挡不住无数业余爱好者，乃至一些专业研究人员公开宣称自己已经找到了答案。学者格哈德·沃金格曾汇总了一份清单，记录了1986年到2016年三十年间出现的116份未经验证的证明文件；这其中，有61份致力于证明 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$，49份认为 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$，还有6份宣称证明了其他结果（比如断言该问题是不可判定的）。^[51] 有些解答甚至曾误导媒体引起短暂的轰动，^[52] 但这些尝试在经历学术审查后最终全都被否定。

电影《推销员 (2012年电影)》（Travelling Salesman）描绘了四位被美国政府秘密聘请试图破解P/NP难题的数学家，在面临道德与国家机器时的挣扎故事。^[53]

在神剧《辛普森一家》第七季第六集“树屋惊魂VI”中，荷马（Homer）意外跌入“三维空间”后，画面背景的特定数字里便出现了 ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ 的彩蛋。^[54][55]

在美剧《基本演绎法》第二季的第二集《求解X》（Solve for X）中，现代版的福尔摩斯和华生调查了几起谋杀案，线索表明受害者都是正致力于解决P/NP问题的数学家。^[56][57]

• R 与 RE 问题的对决，这里的R类地位类似于P类，而RE类则对标了NP类。这两个类别在本质上并不相等，因为在这个体系中，确实存在着拥有无法判定性、但其结果却能够被快速验证的问题，例如归属于RE完全问题的希尔伯特第十问题。^[58]
• 在代数复杂性理论中，也存在着一个类似的问题：VP 与 VNP 之争。它的答案目前与 P/NP 问题一样悬而未决。^[59][58]
• FPT 与 W阶层问题，则是参数化复杂性领域中，对标P/NP架构的同款级难题。

• 指数时间假说
• 计算机科学中的未解问题列表
• 数学中的未解问题列表
• 唯一游戏猜想

• Rachel Crowell. The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved. www.scientificamerican.com. 2021-05-28 [2021-06-21]. This problem concerns the issue of whether questions that are easy to verify (a class of queries called NP) also have solutions that are easy to find (a class called P). 
• William L. Hosch. P versus NP problem mathematics. 大英百科全书. 2009-08-11  [2021-06-20].  请检查|date=中的日期值 (帮助)
• P vs NP Problem. www.claymath.org (Cook, Levin). [2021-06-20]. （原始内容存档于2021-06-18）. Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem... 

• Thomas H. Cormen. Introduction to Algorithms. Cambridge, Massachusetts: MIT Press. 2001. ISBN 978-0-262-03293-3. 
• Michael R. Garey; David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. 1979. ISBN 978-0-7167-1045-5. 
• Oded Goldreich. P, NP, and NP-Completeness. Cambridge, England: Cambridge University Press. 2010. ISBN 978-0-521-12254-2.  Online drafts
• Neil Immerman. Languages that Capture Complexity Classes. SIAM Journal on Computing. 1987, 16 (4): 760–778. CiteSeerX 10.1.1.75.3035 . doi:10.1137/0216051. 
• Christos Papadimitriou. Computational Complexity. Boston, Massachusetts: Addison-Wesley. 1994. ISBN 978-0-201-53082-7. 

• Lance Fortnow; William Gasarch. Computational complexity. 
• Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the 美国计算机协会 (ACM) 2017 Doctoral Dissertation Award.
• P vs. NP and the Computational Complexity Zoo. 2014-08-26. （原始内容存档于2021-11-24） –通过YouTube.