更改

【格式】：翻译方式是另起一个标题板块。翻译不常见人名会在后面的括号中添加英文，而常见的如夏洛克，华生，汤普森则不会。

【格式】：翻译方式是另起一个标题板块。翻译不常见人名会在后面的括号中添加英文，而常见的如夏洛克，华生，汤普森则不会。

【问题】：部分参考文献爬取下来存在格式问题，图片没爬取下来

【问题】：部分参考文献爬取下来存在格式问题，图片没爬取下来

【前言部分】

【前言部分】

P/NP问题是计算机科学领域一个尚未解决的重要问题。它想知道是否每一个问题都既可以快速验证它的解，同时也能快速求解。

P/NP问题是计算机科学领域一个尚未解决的重要问题。它指是否每一个问题都既可以快速验证它的解是否正确，同时也能快速找出它的解。

前面不太严格的表达“快速”指的是，能用多项式时间复杂度的算法来解决任务，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类算法可以在多项式时间内给出答案的问题是“P”或“P类”问题。对一些无法快速求解的问题，如果能提供答案，那么有可能快速验证该答案。能在多项式时间内验证问题的答案，这类问题是NP问题，NP是"nondeterministic polynomial time"的缩写。

前面不太严格的表述“快速”指的是，存在以多项式时间复杂度完成任务的算法，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类算法能在多项式时间内找出答案的问题称为“P”或“P类”问题。对一些无法快速求解的问题，如果能提供答案的相关信息，那么有可能快速验证该答案。这类能在多项式时间内验证答案的问题称为NP问题，NP是"nondeterministic polynomial time"<ref group="注">非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。</ref>的缩写。

对P/NP问题的回答将确定一个问题能否在多项式时间内验证和求解。如果是普遍认为的P≠NP，那么这意味着NP中有一些问题求解比验证更困难：它们不能在多项式时间内求解，但可以在多项式时间内验证。

对P/NP问题的回答将确定一个问题能否在多项式时间内验证和求解。如果是普遍认为的P≠NP，那么这意味着NP中有一些问题求解比验证更困难：它们不能在多项式时间内求解，但可以在多项式时间内验证。

而且 p ≠ NP 仍然保留了 NP 难题的平均格式复杂性。例如，在最坏的情况下，SAT 可能需要一个 EXPTIME，但几乎所有随机选择的实例都是有效可解的。Russell Impagliazzo 描述了五个假设的“世界”，这些世界可能由不同的可能解决方案和平均案例复杂性问题所产生。Impagliazzo，“ a personal view of average-case Complexity,”SCT，pp. 134,10 th Annual Structure in Complexity Theory Conference (SCT’95) ，1995这些范围从“算法米卡”(algorithm mica) ，其中 p = NP 和 SAT 等问题在所有情况下都可以有效地解决，到“ Cryptomania”，其中 p ≠ NP，生成 p 以外问题的硬实例很容易，有三种中间可能性反映 NP 困难实例的不同可能分布。本文把 p 不等于 NP 但 NP 中所有问题在一般情况下都是易处理的“世界”称为“启发式问题”。2009年，普林斯顿大学的一个研讨会研究了五个世界的状态。

而且 p ≠ NP 仍然保留了 NP 难题的平均格式复杂性。例如，在最坏的情况下，SAT 可能需要一个 EXPTIME，但几乎所有随机选择的实例都是有效可解的。Russell Impagliazzo 描述了五个假设的“世界”，这些世界可能由不同的可能解决方案和平均案例复杂性问题所产生。Impagliazzo，“ a personal view of average-case Complexity,”SCT，pp. 134,10 th Annual Structure in Complexity Theory Conference (SCT’95) ，1995这些范围从“算法米卡”(algorithm mica) ，其中 p = NP 和 SAT 等问题在所有情况下都可以有效地解决，到“ Cryptomania”，其中 p ≠ NP，生成 p 以外问题的硬实例很容易，有三种中间可能性反映 NP 困难实例的不同可能分布。本文把 p 不等于 NP 但 NP 中所有问题在一般情况下都是易处理的“世界”称为“启发式问题”。2009年，普林斯顿大学的一个研讨会研究了五个世界的状态。

==不同结论的后果==

==不同结论的影响==

这个问题吸引这么多关注的原因之一是因为潜在答案带来的重大影响。任何一种解决方案的方向都会极大地推动理论进展，或许也会产生巨大的实际影响。

这个问题吸引这么多关注的原因之一是因为潜在答案带来的重大影响。任何一种解决方案的方向都会极大地推动理论进展，或许也会产生巨大的实际影响。

证明结果可能也不会导致NP完全问题的实用算法。该问题的解答不要求多项式的边界很小或是被明确知道。一个没有贡献的证明可以不找到该算法或多项式边界来证明一个解的存在。即使证明是有贡献的，其提供了明确的多项式边界和算法细节，如果多项式不是非常低阶，那么算法在实践中可能不够有效。在这种情况下，理论学家主要会对最初的证明感兴趣，而认识到多项式时间解是可能的将会推动研究找到更好（可能实际有效）的方法。

证明结果可能也不会导致NP完全问题的实用算法。该问题的解答不要求多项式的边界很小或是被明确知道。一个没有贡献的证明可以不找到该算法或多项式边界来证明一个解的存在。即使证明是有贡献的，其提供了明确的多项式边界和算法细节，如果多项式不是非常低阶，那么算法在实践中可能不够有效。在这种情况下，理论学家主要会对最初的证明感兴趣，而认识到多项式时间解是可能的将会推动研究找到更好（可能实际有效）的方法。

一个领域可以被P=NP的证明结果颠覆的例子是密码学，它依赖于某些困难的问题。对于3-SAT这样的NP完全问题，一个有贡献且高效的解答将颠覆多数现有的密码学系统，包括：

一个领域可以被P=NP的证明结果颠覆的例子是密码学，它的基石是某些难解的问题。对于3-SAT这样的NP完全问题，一个有贡献且高效的算法<ref group="注">算法对于加密方式的威胁有多大取决于这个算法有多高效。常数项不是非常大的<math>O(N^2)</math> 算法威胁非常大。如果大多数情况下算法复杂度是<math>\Omega(N^4)</math>，这并不会立刻带来实际性的威胁。</ref>将颠覆大多数现有的密码系统，包括：

*现有的公钥密码的实现，它是当代许多安全应用的基础，比如网上安全金融交易。

*现有的公钥密码的实现，它是当代许多安全应用的基础，比如网上安全金融交易。

*用于通信数据加密的对称密码，比如AES或3DES。

*用于通信数据加密的对称密码，比如AES或3DES。

*加密哈希是比特币等区块链加密货币的基础，用于验证软件更新。对于这些应用程序，要想找到一个有用的映射到给定值的预映像是很困难的，而且理想情况下需要指数级的时间。但如果P=NP，则可以在多项式时间内通过归约为SAT来找到预图像''M''。

*哈希加密，它是比特币等区块链加密货币的基础，用于验证软件更新。对于这些应用程序，要想找到一个有用的映射到给定值的预映像是很困难的，而且理想情况下需要指数级的时间。但如果P=NP，则可以在多项式时间内通过归约为SAT来找到预图像''M''。

这些需要修改或替换为理论上安全的信息解决方案，不内在的基于P-NP不等价。

这些需要修改或替换为理论上安全的信息解决方案，不内在的基于P-NP不等价。

===NP完全问题===

===NP完全问题===

{{Main|NP-completeness}}有许多等价的方式描述NP完全问题。

有许多等价的方式描述NP完全问题。

令''L''是有限字母集合Σ中的一种语言。

令''L''是有限字母集合Σ中的一种语言。

==注解 ==

==注解 ==

{{reflist|group=Note}}

<references group="注" />

==References==

==References==