更改

= = 有理由相信 p ≠ NP 或 p = NP = = Cook 重述了《 P/NP问题的问题: p = NP 吗？.根据民意调查，大多数计算机科学家认为 p 不等于 NP。这种看法的一个关键原因是，在对这些问题进行了几十年的研究之后，还没有人能够为3000多个重要的已知 np 完全问题(见 np 完全问题列表)找到一个多项式时间算法。这些算法在 np- 完全性的概念被定义之前很久就已经被研究过了(第一个发现的 Karp 的21个 np- 完全问题，在它们被证明是 np- 完全的时候都是众所周知的存在问题)。此外，p = NP 的结果可能意味着许多其他目前被认为是错误的令人吃惊的结果，例如 NP = co-NP 和 p = ph。

= = 有理由相信 p ≠ NP 或 p = NP = = Cook 重述了《 P/NP问题的问题: p = NP 吗？.根据民意调查，大多数计算机科学家认为 p 不等于 NP。这种看法的一个关键原因是，在对这些问题进行了几十年的研究之后，还没有人能够为3000多个重要的已知 np 完全问题(见 np 完全问题列表)找到一个多项式时间算法。这些算法在 np- 完全性的概念被定义之前很久就已经被研究过了(第一个发现的 Karp 的21个 np- 完全问题，在它们被证明是 np- 完全的时候都是众所周知的存在问题)。此外，p = NP 的结果可能意味着许多其他目前被认为是错误的令人吃惊的结果，例如 NP = co-NP 和 p = ph。

It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience., point 9.

It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience., point 9.

库克将P与NP问题重述为：P = NP吗？<ref name="Official Problem Description" />根据民意调查的结果，<ref name="poll" /><ref name=":24" />大多数计算机科学家认为P ≠ NP。这种观点的一个主要原因是，经过对这些问题几十年的研究，没有人能够为已知的3000多个重要的NP完全问题找到任何一种多项式时间算法（参见[[wikipedia:List_of_NP-complete_problems|NP完全问题列表]]）。早在NP完全性的概念被定义之前，人们就开始寻找这些算法（在最早发现的NP完全问题中，卡普（Karp）的21个问题是当时非常知名的NP问题）。此外，P = NP这个结论意味着许多其他惊人的结论，而这些结论目前被认为是错误的，例如NP = co-NP和P = PH。

库克将P与NP问题重述为：P = NP吗？<ref name="Official Problem Description" />根据民意调查的结果，<ref name="poll" /><ref name=":24" />大多数计算机科学家认为P ≠ NP。这种观点的一个主要原因是，经过对这些问题几十年的研究，没有人能够为已知的3000多个重要的NP完全问题找到任何一种多项式时间算法（参见[[wikipedia:List_of_NP-complete_problems|NP完全问题列表]]）。早在NP完全性的概念被定义之前，人们就开始寻找这些算法（在最早发现的NP完全问题中，卡普（Karp）的21个问题是当时非常知名的NP问题）。此外，P = NP这个结论意味着许多其他惊人的结论，而这些结论目前被认为是错误的，例如NP = co-NP和P = PH。

也有人凭直觉认为，这些难以求解但找到解后易于验证的问题，它们的存在与现实世界的经验相符。<ref name=":25" /><blockquote>如果P=NP，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方法之间没有巨大的鸿沟。

也有人凭直觉认为，这些难以求解但找到解后易于验证的问题，它们的存在与现实世界的经验相符。<ref>Scott Aaronson. [http://scottaaronson.com/blog/?p=122 "Reasons to believe"]., point 9.</ref><blockquote>如果P=NP，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方法之间没有巨大的鸿沟。

— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）

— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）

</blockquote>

</blockquote>

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

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

*现有公钥密码的实现，<ref name=":26" />它是当代许多安全应用的基础，比如网上安全金融交易。

*现有公钥密码的实现，<ref name=":25" />它是当代许多安全应用的基础，比如网上安全金融交易。

*用于通信数据加密的对称密码，<ref name=":27" />比如AES或3DES。

*用于通信数据加密的对称密码，<ref name=":26" />比如AES或3DES。

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

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

这些需要被信息理论安全方法修改或替换的密码系统潜在的基于P-NP不等性。

这些需要被信息理论安全方法修改或替换的密码系统潜在的基于P-NP不等性。

另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是NP完全的，比如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他的重要问题，如蛋白质结构预测，也是NP完全的；<ref name=":28" />如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。

另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是NP完全的，比如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他的重要问题，如蛋白质结构预测，也是NP完全的；<ref name="Berger" />如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref name=":29" /><ref name=":30" /><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n²），这将产生重大影响。也就是说，这意味着，尽管决策问题（Entscheidungsproblem''）''是不可判定的，数学家的脑力劳动依然完全可以被机器取代。毕竟，人们只需要选择一个足够大的自然数n使得机器无法给出结果时，因而就没有必要再考虑这个问题了。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_=_NP|该节]]】</blockquote>类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说<ref name="Official Problem Description" /><blockquote>... 这使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括CMI奖中的所有问题。</blockquote>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref name=":28" /><ref name=":29" /><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n²），这将产生重大影响。也就是说，这意味着，尽管决策问题（Entscheidungsproblem''）''是不可判定的，数学家的脑力劳动依然完全可以被机器取代。毕竟，人们只需要选择一个足够大的自然数n使得机器无法给出结果时，因而就没有必要再考虑这个问题了。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_=_NP|该节]]】</blockquote>类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说<ref name="Official Problem Description" /><blockquote>... 这使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括CMI奖中的所有问题。</blockquote>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：<ref name=":31" /><blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可行的算法对n个给定的比特进行n^M位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>

唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：<ref name=":30" /><blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可行的算法对n个给定的比特进行n^M位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>

=== P ≠ NP===

=== P ≠ NP===

证明P ≠ NP跟证明P = NP相比缺乏实际计算优势，但它代表了计算复杂性理论的一个重大进步，并对未来的研究提供指导。这将使人们能够以一种严格的方式证明，许多常见问题无法有效解决，因此研究人员可以专注于求出部分解或解其他问题。由于人们普遍相信P ≠ NP，大部分研究已经聚焦于此。<ref name=":32" />

证明P ≠ NP跟证明P = NP相比缺乏实际计算优势，但它代表了计算复杂性理论的一个重大进步，并对未来的研究提供指导。这将使人们能够以一种严格的方式证明，许多常见问题无法有效解决，因此研究人员可以专注于求出部分解或解其他问题。由于人们普遍相信P ≠ NP，大部分研究已经聚焦于此。<ref name=":31" />

P ≠ NP仍然保留着NP中困难问题的平均复杂度。例如，SAT在最坏的情况下可能需要指数级的时间，但几乎所有随机选择的实例都可以有效解决。拉塞尔·英帕利亚佐（Russell Impagliazzo）描述了五个假设的“世界”，这五个“世界”源于对平均复杂性问题的不同可能回答。<ref name=":33" />范围从“算法”（Algorithmica）世界，这个世界中 P = NP 和像 SAT 这样的问题中的所有例子都可以有效解决，到“密码狂热”（Cryptomania）世界，这个世界是 P ≠ NP 并且容易生成在 P 之外的困难问题，<u>其中有着三种可能性，它们反映了NP难问题中不同可能的难度分布。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_%E2%89%A0_NP|这节的]]第二段倒数第三句with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. 】在这篇论文中，“启发式”（Heuristica）是这样一个“世界”，P ≠ NP但NP中的大部分问题都是比较容易解决的。2009年，普林斯顿大学的一个研讨会研究了五个世界的现状。<ref name=":34" />

P ≠ NP仍然保留着NP中困难问题的平均复杂度。例如，SAT在最坏的情况下可能需要指数级的时间，但几乎所有随机选择的实例都可以有效解决。拉塞尔·英帕利亚佐（Russell Impagliazzo）描述了五个假设的“世界”，这五个“世界”源于对平均复杂性问题的不同可能回答。<ref name=":33" />范围从“算法”（Algorithmica）世界，这个世界中 P = NP 和像 SAT 这样的问题中的所有例子都可以有效解决，到“密码狂热”（Cryptomania）世界，这个世界是 P ≠ NP 并且容易生成在 P 之外的困难问题，<u>其中有着三种可能性，它们反映了NP难问题中不同可能的难度分布。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_%E2%89%A0_NP|这节的]]第二段倒数第三句with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. 】在这篇论文中，“启发式”（Heuristica）是这样一个“世界”，P ≠ NP但NP中的大部分问题都是比较容易解决的。2009年，普林斯顿大学的一个研讨会研究了五个世界的现状。<ref name=":34" />