更改

=== P ≠ NP===

=== P ≠ NP===

证明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跟证明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">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>

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>