134
个编辑
更改
跳到导航
跳到搜索
小第502行：
第502行： − + 第509行：
第509行： − +
→声称的解答
==Claimed solutions <span id="Deolalikar"></span>==
==Claimed solutions <span id="Deolalikar"></span>==
While the P versus NP problem is generally considered unsolved,<ref>{{Cite news|author=[[John Markoff]] |url=https://www.nytimes.com/2009/10/08/science/Wpolynom.html |title=Prizes Aside, the P-NP Puzzler Has Consequences|newspaper=The New York Times|date=8 October 2009}}</ref> many amateur and some professional researchers have claimed solutions. [[Gerhard J. Woeginger]] maintains a list that, as of 2016, contains 62 purported proofs of P = NP, 50 proofs of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable.<ref>{{Cite web|title=The P-versus-NP page|url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm|author=Gerhard J. Woeginger|author-link=Gerhard J. Woeginger|access-date=2018-06-24}}</ref> Some attempts at resolving P versus NP have received brief media attention,<ref name="NYT2010">{{Cite news|last=Markoff|first=John|title=Step 1: Post Elusive Proof. Step 2: Watch Fireworks. |url=https://www.nytimes.com/2010/08/17/science/17proof.html?_r=1 |access-date=20 September 2010|newspaper=The New York Times|date=16 August 2010}}</ref> though these attempts have since been refuted.
While the P versus NP problem is generally considered unsolved,<ref name=":24">{{Cite news|author=[[John Markoff]] |url=https://www.nytimes.com/2009/10/08/science/Wpolynom.html |title=Prizes Aside, the P-NP Puzzler Has Consequences|newspaper=The New York Times|date=8 October 2009}}</ref> many amateur and some professional researchers have claimed solutions. [[Gerhard J. Woeginger]] maintains a list that, as of 2016, contains 62 purported proofs of P = NP, 50 proofs of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable.<ref name=":28">{{Cite web|title=The P-versus-NP page|url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm|author=Gerhard J. Woeginger|author-link=Gerhard J. Woeginger|access-date=2018-06-24}}</ref> Some attempts at resolving P versus NP have received brief media attention,<ref name="NYT2010">{{Cite news|last=Markoff|first=John|title=Step 1: Post Elusive Proof. Step 2: Watch Fireworks. |url=https://www.nytimes.com/2010/08/17/science/17proof.html?_r=1 |access-date=20 September 2010|newspaper=The New York Times|date=16 August 2010}}</ref> though these attempts have since been refuted.
While the P versus NP problem is generally considered unsolved, many amateur and some professional researchers have claimed solutions. Gerhard J. Woeginger maintains a list that, as of 2016, contains 62 purported proofs of P = NP, 50 proofs of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable. Some attempts at resolving P versus NP have received brief media attention, though these attempts have since been refuted.
While the P versus NP problem is generally considered unsolved, many amateur and some professional researchers have claimed solutions. Gerhard J. Woeginger maintains a list that, as of 2016, contains 62 purported proofs of P = NP, 50 proofs of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable. Some attempts at resolving P versus NP have received brief media attention, though these attempts have since been refuted.
==声称的解答==
==声称的解答==
虽然P/NP问题通常被认为是不可解决的，许多业余和一些专业研究人员声称提出了解决方法。格哈德·J·沃金（Gerhard J.Woeginger）维护着一份列表，截至2016年，该表包含62个据称是P = NP的证明，50个P ≠ NP的证明，2个问题不可证明的证明，1个问题不可判定的证明。一些试图解决P/NP的尝试得到了媒体的短暂关注，尽管这些尝试后来遭到了反驳。
虽然P/NP问题通常被认为是不可解决的，<ref name=":24" />许多业余和一些专业研究人员声称提出了解决方法。格哈德·J·沃金（Gerhard J.Woeginger）维护着一份列表，截至2016年，该表包含62个据称是P = NP的证明，50个P ≠ NP的证明，2个问题不可证明的证明，1个问题不可判定的证明。<ref name=":28" />一些试图解决P/NP的尝试得到了媒体的短暂关注，<ref name="NYT2010" />尽管这些尝试后来遭到了反驳。
==Logical characterizations==
==Logical characterizations==