更改

这些障碍是 NP 完全问题有用的另一个原因: 如果一个 NP 完全问题的多项式时间算法可以证明，这将解决 p = NP 问题的方式不排除上述结果。

这些障碍是 NP 完全问题有用的另一个原因: 如果一个 NP 完全问题的多项式时间算法可以证明，这将解决 p = NP 问题的方式不排除上述结果。

These barriers have also led some computer scientists to suggest that the P versus NP problem may be [[Independence (mathematical logic)|independent]] of standard axiom systems like [[ZFC]] (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it is impossible to prove in ZFC that such algorithms are correct.<ref>{{Cite web|url=http://www.scottaaronson.com/papers/indep.pdf|first=Scott|last=Aaronson|author-link=Scott Aaronson|title=Is P Versus NP Formally Independent?}}.</ref> However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the [[Peano axioms]] (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.<ref>{{Cite journal|title=On the independence of P versus NP|first1=Shai|last1=Ben-David |first2=Shai|last2=Halevi |series=Technical Report|volume=714|publisher=Technion|year=1992|url=https://www.cs.technion.ac.il/~shai/ph.ps.gz}}.</ref> Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

These barriers have also led some computer scientists to suggest that the P versus NP problem may be [[Independence (mathematical logic)|independent]] of standard axiom systems like [[ZFC]] (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it is impossible to prove in ZFC that such algorithms are correct.<ref name=":36">{{Cite web|url=http://www.scottaaronson.com/papers/indep.pdf|first=Scott|last=Aaronson|author-link=Scott Aaronson|title=Is P Versus NP Formally Independent?}}.</ref> However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the [[Peano axioms]] (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.<ref name=":37">{{Cite journal|title=On the independence of P versus NP|first1=Shai|last1=Ben-David |first2=Shai|last2=Halevi |series=Technical Report|volume=714|publisher=Technion|year=1992|url=https://www.cs.technion.ac.il/~shai/ph.ps.gz}}.</ref> Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

These barriers have also led some computer scientists to suggest that the P versus NP problem may be independent of standard axiom systems like ZFC (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it is impossible to prove in ZFC that such algorithms are correct.. However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the Peano axioms (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.. Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

These barriers have also led some computer scientists to suggest that the P versus NP problem may be independent of standard axiom systems like ZFC (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it is impossible to prove in ZFC that such algorithms are correct.. However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the Peano axioms (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.. Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

|-

|-

|相对证明

|相对证明

|想象这样一个世界，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有神谕的世界，无论oracle做什么。这些证明被称为相对化。1975年，贝克、吉尔和索洛维证明，对于某些oracle，P=NP，而对于其他oracle，P ≠ NP。由于相对化证据只能证明对所有可能的预言都一致正确的陈述，这表明相对化证据无法解决P=NP。

|想象这样一个世界，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有oracle的世界，无论oracle做什么。这被称为相对证明。1975年，贝克（Baker,）、吉尔（Gill）和索洛维（Solovay）证明，对于某些oracle，P = NP，而对于其他oracle，P ≠ NP。<ref name=":32" />由于相对证明只能证明对所有可能的oracle都一致正确的陈述，这表明相对证明技术无法解决P = NP。

|-

|-

|自然证明

|自然证明

|1993年，亚历山大·拉兹博罗夫（Alexander Razborov）和史蒂文·鲁迪奇（Steven Rudich）为电路复杂度下限定义了一类通用的证明技术，称为自然证明。当时，所有已知的电路下界都是自然的，电路复杂性被认为是解决P=NP的一种非常有前途的方法。然而Razborov和Razich证明如果单向函数存在，那么没有一种自然证明法可以区分P和NP。虽然单向函数从未被正式证明存在，但大多数数学家认为它们确实存在，证明它们存在的证据将比P≠ NP更有力。因此，仅自然证明不太可能解决P=NP。

|1993年，亚历山大·拉兹博罗夫（Alexander Razborov）和史蒂文·鲁迪奇（Steven Rudich）为电路复杂度下限定义了一类通用的证明技术，称为自然证明。<ref name=":33" />当时，所有已知的电路下界都是自然的，电路复杂性被认为是解决P=NP的一种非常有前途的方法。然而拉兹博罗夫（Razborov）和鲁迪奇（Razich）证明如果单向函数存在，那么没有一种自然证明法可以区分P和NP。虽然单向函数从未被正式证明存在，但大多数数学家认为它们确实存在，并且它们存在性的证明将比P ≠ NP强的多。因此，仅用自然证明不太可能解决P = NP。

|-

|-

|代数证明

|代数证明

|在Baker-Gill-Solovay结果之后，新的非相对化证明技术被成功地用于证明IP=PSPACE。然而，在2008年，Scott Aaronson和Avi Wigderson证明了IP=PSPACE证明中使用的主要技术工具，即所谓的算术化，也不足以解决P=NP问题。

|在Baker-Gill-Solovay结果之后，新的非相对证明技术被成功地用于证明IP = PSPACE。然而，在2008年，斯科特·阿伦森（Scott Aaronson）和阿维·维格德森（Avi Wigderson）证明了在IP = PSPACE证明中使用的主要技术工具，即所谓的算术化，也不足以解决P = NP问题。<ref name=":34" />

|}

|}

这些障碍是NP完全问题有意义的另一个原因：如果可以为NP完全问题有多项式时间算法，这将以不被以上结果排除的方式解决P=NP问题。

这些障碍是NP完全问题有用的另一个原因：如果NP完全问题有多项式时间算法，这将以不被以上结果排除的方式解决P=NP问题。

==Claimed solutions <span id="Deolalikar"></span>==

==Claimed solutions <span id="Deolalikar"></span>==