134
个编辑
更改
跳到导航
跳到搜索
小第299行：
第299行： − + − + 第331行：
第331行： − + − + 第378行：
第378行： − + 第395行：
第395行： − + 第401行：
第401行： − + 第408行：
第408行： − 这个问题吸引这么多关注的原因之一是因为潜在答案带来的重大影响。任何一种解决方案的方向都会极大地推动理论进展，或许也会产生巨大的实际影响。+ − + − 证明结果可能也不会导致NP完全问题的实用算法。该问题的解答不要求多项式的边界很小或是被明确知道。一个没有贡献的证明可以不找到该算法或多项式边界来证明一个解的存在。即使证明是有贡献的，其提供了明确的多项式边界和算法细节，如果多项式不是非常低阶，那么算法在实践中可能不够有效。在这种情况下，理论学家主要会对最初的证明感兴趣，而认识到多项式时间解是可能的将会推动研究找到更好（可能实际有效）的方法。+ − + − + − + − + − 这些需要修改或替换为理论上安全的信息解决方案，不内在的基于P-NP不等价。+ − 另一方面，许多目前在数学上棘手的问题变得容易处理。例如，运筹学中的许多问题都是NP完全的，例如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他重要问题，如蛋白质结构预测，也是NP完全的；如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。+ − 但这种变化的重要性与解决NP完全问题的有效方法带给数学本身所引发的革命相比就相形见绌了。哥德尔在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<blockquote>如果真的有一台机器φ(n)∼ K⋅ n（甚至∼ K⋅ n<sup>2</sup>），这将产生重大影响。也就是说，这意味着，尽管Entscheidungsproblem是不可判定的，数学家的脑力劳动可以完全被机器所取代。毕竟，人们只需要选择自然数n，它太大了，以至于当机器无法给出结果时，就没有必要再考虑这个问题。</blockquote>类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说<blockquote>... 这让使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括所有CMI奖中的问题。</blockquote>数学研究人员在他们的职业生涯中一直在证明定理，有些证明在问题提出后花了几十年甚至几个世纪才找到。例如，费马最后定理花了三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。+ − Donald Knuth表示，他已经开始相信P=NP，但对可能的证明结果所带来的影响持保留态度：<blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可能的算法对n个给定的比特进行n<sup>M</sup>位、加法或移位运算，很难相信所有这些算法都失败了。然而，我的主要观点是，我不相信等式P=NP会有帮助，即使它被证明了，因为这样的证明几乎肯定是没有贡献的。</blockquote>+ − 证明P≠ NP跟P=NP相比缺乏实际计算优势，但它代表了计算复杂性理论的一个重大进步，并为未来的研究提供了指导。这将使人们能够以一种严格的方式表明，许多常见问题无法有效解决，因此研究人员的注意力可以集中在部分解或其他问题的解上。由于人们普遍相信P≠ NP，已经大部分聚焦于这种研究。+ − P≠ NP仍然保留着NP中困难问题的平均案例复杂性。例如，SAT在最坏的情况下可能需要指数级的时间，但几乎所有随机选择的实例都可以有效解决。Russell Impagliazzo描述了五个假设的“世界”，这五个“世界”来自对平均案例复杂性问题的不同可能回答。这些范围从“算法”，其中 P = NP 和像 SAT 这样的问题可以在所有情况下有效地解决，到“密码狂热”，其中 P ≠ NP 并且在 P 之外生成困难问题很容易，三种中间可能性反映了不同的可能 NP-hard问题实例的难度分布。在这篇论文中，P≠NP但平均来看NP中的所有问题都是容易解决的，这个“世界”称为“启发式”。2009年，普林斯顿大学的一个研讨会研究了五个世界的现状。+ 第448行：
第448行： − + − + − +
→不同结论的影响
— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）
— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）
</blockquote>
</blockquote>
另一方面，一些研究人员认为，人们过于相信P ≠ NP了，研究人员也应该探索P = NP的证明。例如，2002年有如下观点：
另一方面，一些研究人员认为，人们过于相信P ≠ NP了，研究人员也应该探索P = NP的证明。例如，2002年有如下观点：<ref name="poll" />
<blockquote>支持P ≠ NP主要是因为在穷举搜索领域缺乏重大进展。在我看来，这是一个非常薄弱的论点。算法的搜索空间非常大，我们才刚刚开始探索。[...] 费马最后定理的证明也表明，非常简单的问题只能通过非常深刻的理论来解决。<ref name="poll" />
<blockquote>支持P ≠ NP主要是因为在穷举搜索领域缺乏重大进展。在我看来，这是一个非常薄弱的论点。算法的搜索空间非常大，我们才刚刚开始探索。[...] 费马最后定理的证明也表明，非常简单的问题只能通过非常深刻的理论来解决。
— 莫斯·Y·瓦迪，莱斯大学（Moshe Y. Vardi, Rice University）
— 莫斯·Y·瓦迪，莱斯大学（Moshe Y. Vardi, Rice University）
* Existing implementations of [[public-key cryptography]],<ref name=":25">See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997
* Existing implementations of [[public-key cryptography]],<ref name=":25">See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997
|publisher=Springer |arxiv=cs/9809117 |bibcode=1998cs........9117H |doi=10.1007/3-540-63890-3_4 |series=Lecture Notes in Computer Science |isbn=978-3-540-63890-2 |volume=1350}} for a reduction of factoring to SAT. A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.</ref> a foundation for many modern security applications such as secure financial transactions over the Internet.
|publisher=Springer |arxiv=cs/9809117 |bibcode=1998cs........9117H |doi=10.1007/3-540-63890-3_4 |series=Lecture Notes in Computer Science |isbn=978-3-540-63890-2 |volume=1350}} for a reduction of factoring to SAT. A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.</ref> a foundation for many modern security applications such as secure financial transactions over the Internet.
*[[Symmetric cipher]]s such as [[Advanced Encryption Standard|AES]] or [[Triple DES|3DES]],<ref>See, for example, {{cite journal |title=Logical cryptanalysis as a SAT problem |author1=Massacci, F. |author2=Marraro, L. |name-list-style=amp |journal=Journal of Automated Reasoning |volume=24 |issue=1 |pages=165–203 |year=2000 |citeseerx=10.1.1.104.962 |doi=10.1023/A:1006326723002|s2cid=3114247 }} in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.</ref> used for the encryption of communications data.
*[[Symmetric cipher]]s such as [[Advanced Encryption Standard|AES]] or [[Triple DES|3DES]],<ref name=":26">See, for example, {{cite journal |title=Logical cryptanalysis as a SAT problem |author1=Massacci, F. |author2=Marraro, L. |name-list-style=amp |journal=Journal of Automated Reasoning |volume=24 |issue=1 |pages=165–203 |year=2000 |citeseerx=10.1.1.104.962 |doi=10.1023/A:1006326723002|s2cid=3114247 }} in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.</ref> used for the encryption of communications data.
*[[Cryptographic hash function|Cryptographic hashing]], which underlies [[blockchain]] [[cryptocurrency|cryptocurrencies]] such as [[Bitcoin]], and is used to authenticate software updates. For these applications, the problem of finding a pre-image that hashes to a given value must be difficult in order to be useful, and ideally should require exponential time. However, if P = NP, then finding a pre-image ''M'' can be done in polynomial time, through reduction to SAT.<ref>{{cite conference |title=Inversion attacks on secure hash functions using SAT solvers
*[[Cryptographic hash function|Cryptographic hashing]], which underlies [[blockchain]] [[cryptocurrency|cryptocurrencies]] such as [[Bitcoin]], and is used to authenticate software updates. For these applications, the problem of finding a pre-image that hashes to a given value must be difficult in order to be useful, and ideally should require exponential time. However, if P = NP, then finding a pre-image ''M'' can be done in polynomial time, through reduction to SAT.<ref name=":27">{{cite conference |title=Inversion attacks on secure hash functions using SAT solvers
|author1=De, Debapratim |author2=Kumarasubramanian, Abishek |author3=Venkatesan, Ramarathnam
|author1=De, Debapratim |author2=Kumarasubramanian, Abishek |author3=Venkatesan, Ramarathnam
|book-title=Theory and Applications of Satisfiability Testing--SAT 2007
|book-title=Theory and Applications of Satisfiability Testing--SAT 2007
研究领域的数学家们毕生致力于证明定理，有些证明甚至需要几十年甚至几百年的时间才能找到，例如，费马最后定理的证明花了三个多世纪。如果存在一种“合理”规模的方法，那么这种方法就能保证找到定理的证明，从本质上结束这种斗争。
研究领域的数学家们毕生致力于证明定理，有些证明甚至需要几十年甚至几百年的时间才能找到，例如，费马最后定理的证明花了三个多世纪。如果存在一种“合理”规模的方法，那么这种方法就能保证找到定理的证明，从本质上结束这种斗争。
[[Donald Knuth]] has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:<ref>{{cite book|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a|title=Twenty Questions for Donald Knuth|date=20 May 2014|work=informit.com|publisher=[[InformIT (publisher)|InformIT]]|last=Knuth|first=Donald E.|author-link=Donald Knuth|access-date=20 July 2014}}</ref>
[[Donald Knuth]] has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:<ref name=":28">{{cite book|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a|title=Twenty Questions for Donald Knuth|date=20 May 2014|work=informit.com|publisher=[[InformIT (publisher)|InformIT]]|last=Knuth|first=Donald E.|author-link=Donald Knuth|access-date=20 July 2014}}</ref>
<nowiki>{{quote|1=[...] if you imagine a number M that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do n</nowiki><sup>M</sup> bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.
<nowiki>{{quote|1=[...] if you imagine a number M that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do n</nowiki><sup>M</sup> bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.
===P ≠ NP===
===P ≠ NP===
A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.<ref>{{Cite journal|title=The Heuristic Problem-Solving Approach |author=L. R. Foulds |journal=[[Journal of the Operational Research Society]] |volume=34 |issue=10 |date=October 1983 |pages=927–934 |jstor=2580891 |doi=10.2307/2580891}}</ref>
A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.<ref name=":29">{{Cite journal|title=The Heuristic Problem-Solving Approach |author=L. R. Foulds |journal=[[Journal of the Operational Research Society]] |volume=34 |issue=10 |date=October 1983 |pages=927–934 |jstor=2580891 |doi=10.2307/2580891}}</ref>
A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.
A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.
= = = = p ≠ NP = = = 证明 p ≠ NP 缺乏证明 p = NP 的实际计算效益，但仍代表了计算复杂性理论的一个重大进展，并为未来的研究提供了指导。这将使人们能够以正式的方式表明许多共同的问题无法有效地解决，从而使研究人员的注意力能够集中在其他问题的部分解决或解决方案上。由于人们普遍相信 p 不等于 NP，这种研究的焦点大部分已经开始了。
= = = = p ≠ NP = = = 证明 p ≠ NP 缺乏证明 p = NP 的实际计算效益，但仍代表了计算复杂性理论的一个重大进展，并为未来的研究提供了指导。这将使人们能够以正式的方式表明许多共同的问题无法有效地解决，从而使研究人员的注意力能够集中在其他问题的部分解决或解决方案上。由于人们普遍相信 p 不等于 NP，这种研究的焦点大部分已经开始了。
Also P ≠ NP still leaves open the [[average-case complexity]] of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. [[Russell Impagliazzo]] has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.<ref>R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps "A personal view of average-case complexity,"] sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995</ref> These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A [[Princeton University]] workshop in 2009 studied the status of the five worlds.<ref>{{Cite web|url = http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/|title = Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"|archive-url = https://web.archive.org/web/20131115034042/http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/|archive-date = 2013-11-15}}</ref>
Also P ≠ NP still leaves open the [[average-case complexity]] of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. [[Russell Impagliazzo]] has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.<ref name=":30">R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps "A personal view of average-case complexity,"] sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995</ref> These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A [[Princeton University]] workshop in 2009 studied the status of the five worlds.<ref name=":31">{{Cite web|url = http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/|title = Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"|archive-url = https://web.archive.org/web/20131115034042/http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/|archive-date = 2013-11-15}}</ref>
Also P ≠ NP still leaves open the average-case complexity of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. Russell Impagliazzo has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995 These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A Princeton University workshop in 2009 studied the status of the five worlds.
Also P ≠ NP still leaves open the average-case complexity of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. Russell Impagliazzo has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995 These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A Princeton University workshop in 2009 studied the status of the five worlds.
==不同结论的影响==
==不同结论的影响==
这个问题吸引这么多关注的原因之一是因为潜在结论带来的重大影响。任何一种解决方法的思路都会极大地推动理论进展，或许也会因此产生巨大影响。
===P = NP===
===P = NP===
如果P=NP的证明能为NP中的一些重要问题提供高效的方法，那么该证明会有惊人的实际影响。由于许多不同的NP完全问题在许多领域意义重大，因此产生了潜在的有积极的和消极的影响。
如果P = NP的证明能为NP中的一些重要问题提供高效的方法，那么该证明会有惊人的影响。由于许多不同的NP完全问题在许多领域意义重大，这产生了潜在的或积极或消极的影响。
证明的结果可能也不会带来NP完全问题的实用算法。该问题的解答不要求多项式的边界很小甚至被明确知道。一个没有贡献的证明可以避开该算法或多项式边界来证明一个解的存在。即使证明是有贡献的，其提供了明确的多项式边界和算法细节，如果多项式不是非常低阶的，那么算法在实际中可能不够有效。在这种情况下，理论学家主要会对最初的证明感兴趣，而认识到多项式时间解的可能性将会推动研究找到更好（可能实际有效）的方法。
一个领域可以被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" />它是当代许多安全应用的基础，比如网上安全金融交易。
*用于通信数据加密的对称密码，比如AES或3DES。
*用于通信数据加密的对称密码，<ref name=":27" />比如AES或3DES。
*哈希加密，它是比特币等区块链加密货币的基础，用于验证软件更新。对于这些应用程序，要想找到一个有用的映射到给定值的预映像是很困难的，而且理想情况下需要指数级的时间。但如果P=NP，则可以在多项式时间内通过归约为SAT来找到预图像''M''。
*哈希加密，它是比特币等区块链加密货币的基础，用于验证软件更新。对于这些应用程序，要想找到一个有用的映射到给定值的预映像是很困难的，而且理想情况下需要指数级的时间。但如果P = NP，则可以在多项式时间内通过归约为SAT来找到预映像''M''。<ref name="Berger" />
这些需要被信息理论安全方法修改或替换的密码系统潜在的基于P-NP不等性。
另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是NP完全的，比如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他的重要问题，如蛋白质结构预测，也是NP完全的；<ref name=":28" />如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。
但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref name=":29" /><ref name=":30" /><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n<sup>2</sup>），这将产生重大影响。也就是说，这意味着，尽管决策问题（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<sup>M</sup>位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>
=== P ≠ NP===
=== P ≠ NP===
证明P ≠ NP跟证明P = NP相比缺乏实际计算优势，但它代表了计算复杂性理论的一个重大进步，并对未来的研究提供指导。这将使人们能够以一种严格的方式证明，许多常见问题无法有效解决，因此研究人员可以专注于求出部分解或解其他问题。由于人们普遍相信P ≠ NP，大部分研究已经聚焦于此。<ref name=":32" />
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" />
==Results about difficulty of proof==
==Results about difficulty of proof==
|-
|-
|[[Relativizing proof]]s
|[[Relativizing proof]]s
|Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an ''[[oracle machine|oracle]]'' (a black box which can answer a fixed set of questions in constant time, such as a black box that solves any given traveling salesman problem in 1 step), and the running time of the oracle is not counted against the running time of the algorithm. Most proofs (especially classical ones) apply uniformly in a world with oracles regardless of what the oracle does. These proofs are called ''relativizing''. In 1975, Baker, Gill, and [[Robert M. Solovay|Solovay]] showed that P = NP with respect to some oracles, while P ≠ NP for other oracles.<ref>{{cite journal |author1=T. P. Baker |author2=J. Gill |author3=R. Solovay. |title=Relativizations of the P =? NP Question |journal=[[SIAM Journal on Computing]] |volume=4 |issue=4 |pages=431–442 |year=1975 |doi=10.1137/0204037}}</ref> Since relativizing proofs can only prove statements that are uniformly true with respect to all possible oracles, this showed that relativizing techniques cannot resolve P = NP.
|Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an ''[[oracle machine|oracle]]'' (a black box which can answer a fixed set of questions in constant time, such as a black box that solves any given traveling salesman problem in 1 step), and the running time of the oracle is not counted against the running time of the algorithm. Most proofs (especially classical ones) apply uniformly in a world with oracles regardless of what the oracle does. These proofs are called ''relativizing''. In 1975, Baker, Gill, and [[Robert M. Solovay|Solovay]] showed that P = NP with respect to some oracles, while P ≠ NP for other oracles.<ref name=":32">{{cite journal |author1=T. P. Baker |author2=J. Gill |author3=R. Solovay. |title=Relativizations of the P =? NP Question |journal=[[SIAM Journal on Computing]] |volume=4 |issue=4 |pages=431–442 |year=1975 |doi=10.1137/0204037}}</ref> Since relativizing proofs can only prove statements that are uniformly true with respect to all possible oracles, this showed that relativizing techniques cannot resolve P = NP.
|-
|-
|[[Natural proof]]s
|[[Natural proof]]s
| In 1993, [[Alexander Razborov]] and [[Steven Rudich]] defined a general class of proof techniques for circuit complexity lower bounds, called ''[[natural proof]]s''.<ref>{{cite journal |author1=Razborov, Alexander A. |author2=Steven Rudich |title=Natural proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |year=1997 |pages=24–35 |doi=10.1006/jcss.1997.1494|doi-access=free }}</ref> At the time all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P = NP. However, Razborov and Rudich showed that, if [[one-way functions]] exist, then no natural proof method can distinguish between P and NP. Although one-way functions have never been formally proven to exist, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can resolve P = NP.
| In 1993, [[Alexander Razborov]] and [[Steven Rudich]] defined a general class of proof techniques for circuit complexity lower bounds, called ''[[natural proof]]s''.<ref name=":33">{{cite journal |author1=Razborov, Alexander A. |author2=Steven Rudich |title=Natural proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |year=1997 |pages=24–35 |doi=10.1006/jcss.1997.1494|doi-access=free }}</ref> At the time all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P = NP. However, Razborov and Rudich showed that, if [[one-way functions]] exist, then no natural proof method can distinguish between P and NP. Although one-way functions have never been formally proven to exist, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can resolve P = NP.
|-
|-
|Algebrizing proofs
|Algebrizing proofs
|After the Baker-Gill-Solovay result, new non-relativizing proof techniques were successfully used to prove that [[IP (complexity)|IP]] = [[PSPACE]]. However, in 2008, [[Scott Aaronson]] and [[Avi Wigderson]] showed that the main technical tool used in the IP = PSPACE proof, known as ''arithmetization'', was also insufficient to resolve P = NP.<ref>{{cite conference |author1=S. Aaronson |author2=A. Wigderson |name-list-style=amp |title=Algebrization: A New Barrier in Complexity Theory |conference=Proceedings of ACM STOC'2008 |year=2008 |url=http://www.scottaaronson.com/papers/alg.pdf |doi=10.1145/1374376.1374481 |pages=731–740}}</ref>
|After the Baker-Gill-Solovay result, new non-relativizing proof techniques were successfully used to prove that [[IP (complexity)|IP]] = [[PSPACE]]. However, in 2008, [[Scott Aaronson]] and [[Avi Wigderson]] showed that the main technical tool used in the IP = PSPACE proof, known as ''arithmetization'', was also insufficient to resolve P = NP.<ref name=":34">{{cite conference |author1=S. Aaronson |author2=A. Wigderson |name-list-style=amp |title=Algebrization: A New Barrier in Complexity Theory |conference=Proceedings of ACM STOC'2008 |year=2008 |url=http://www.scottaaronson.com/papers/alg.pdf |doi=10.1145/1374376.1374481 |pages=731–740}}</ref>
|}
|}