更改

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

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

但这种变化的重要性与解决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>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref>History of this letter and its translation from Michael Sipser. [["The History and Status of the P versus NP question"]]</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>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：<ref name=":30" /><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，大部分研究已经聚焦于此。<ref name=":31" />

证明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年，普林斯顿大学的一个研讨会研究了五个世界的现状。

==Results about difficulty of proof==

==Results about difficulty of proof==