更改

研究领域的数学家们毕生致力于证明定理，有些证明甚至需要几十年甚至几百年的时间才能找到，例如，费马最后定理的证明花了三个多世纪。如果存在一种“合理”规模的方法，那么这种方法就能保证找到定理的证明，从本质上结束这种斗争。

研究领域的数学家们毕生致力于证明定理，有些证明甚至需要几十年甚至几百年的时间才能找到，例如，费马最后定理的证明花了三个多世纪。如果存在一种“合理”规模的方法，那么这种方法就能保证找到定理的证明，从本质上结束这种斗争。

[[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>

[[Donald Knuth]] has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof<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>^M 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>^M bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.

Donald Knuth has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:

Donald Knuth has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:

===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 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.

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 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. 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.

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.

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

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

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

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

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

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

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

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

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref>History of this letter and its translation from Michael Sipser. [http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf "The History and Status of the P versus NP question"] (PDF).</ref><ref>David S. Johnson (2012). [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 "A Brief History of NP-Completeness, 1954–2012"]. [[wikipedia:CiteSeerX_(identifier)|CiteSeerX]] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 10.1.1.399.1480]. From pages 359–376 of Optimization Stories, [[wikipedia:Martin_Grötschel|M. Grötschel]] (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.</ref><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>History of this letter and its translation from Michael Sipser. [http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf "The History and Status of the P versus NP question"] (PDF).</ref><ref>David S. Johnson (2012). [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 "A Brief History of NP-Completeness, 1954–2012"]. [[wikipedia:CiteSeerX_(identifier)|CiteSeerX]] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 10.1.1.399.1480]. From pages 359–376 of Optimization Stories, [[wikipedia:Martin_Grötschel|M. Grötschel]] (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.</ref><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n²），这将产生重大影响。也就是说，这意味着，尽管决策问题（Entscheidungsproblem''）''是不可判定的，数学家的脑力劳动依然完全可以被机器取代。毕竟，人们只需要选择一个足够大的自然数n使得机器无法给出结果时，因而就没有必要再考虑这个问题了。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_=_NP|该节]]】</blockquote>类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说<ref name=":35" /><blockquote>... 这使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括CMI奖中的所有问题。</blockquote>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

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

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

=== P ≠ NP===

=== P ≠ NP===

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

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

P ≠ NP仍然保留着NP中困难问题的平均复杂度。例如，SAT在最坏的情况下可能需要指数级的时间，但几乎所有随机选择的实例都可以有效解决。拉塞尔·英帕利亚佐（Russell Impagliazzo）描述了五个假设的“世界”，这五个“世界”源于对平均复杂性问题的不同可能回答。<ref name=":30" />范围从“算法”（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=":31" />

P ≠ NP仍然保留着NP中困难问题的平均复杂度。例如，SAT在最坏的情况下可能需要指数级的时间，但几乎所有随机选择的实例都可以有效解决。拉塞尔·英帕利亚佐（Russell Impagliazzo）描述了五个假设的“世界”，这五个“世界”源于对平均复杂性问题的不同可能回答。<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>范围从“算法”（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=":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>

==Results about difficulty of proof==

==Results about difficulty of proof==