Talk:NP complexity class: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Daniel Mietchen
imported>Daniel Mietchen
Line 35: Line 35:


::::::An [http://cacm.acm.org/blogs/blog-cacm/97587-a-tale-of-a-serious-attempt-at-p%E2%89%A0np/fulltext introduction to non-specialists] by [[Richard J. Lipton]], one of the specialists involved with verifying the proof. --[[User:Daniel Mietchen|Daniel Mietchen]] 12:23, 17 August 2010 (UTC)
::::::An [http://cacm.acm.org/blogs/blog-cacm/97587-a-tale-of-a-serious-attempt-at-p%E2%89%A0np/fulltext introduction to non-specialists] by [[Richard J. Lipton]], one of the specialists involved with verifying the proof. --[[User:Daniel Mietchen|Daniel Mietchen]] 12:23, 17 August 2010 (UTC)
:::::::[http://www.danhagon.me.uk/PvsNP/PvsNP_timeline.html Timeline]. --[[User:Daniel Mietchen|Daniel Mietchen]] 23:22, 17 August 2010 (UTC)

Revision as of 18:22, 17 August 2010

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
To learn how to update the categories for this article, see here. To update categories, edit the metadata template.
 Definition Class of decision problems that can be solved in nondeterministic polynomial time or, equivalently, can be checked in polynomial time. [d] [e]
Checklist and Archives
 Workgroup categories Mathematics and Computers [Please add or review categories]
 Talk Archive none  English language variant British English

TODO:

  • Add formal definitions for P, NP, reduction
  • Add citations everywhere
  • Make branch and bound section
  • add disambiguation page for "NP" that links here

--Warren Schudy 23:55, 12 November 2007 (CST) Why does the subpages template produce that green notice about seeking approval? This article is far from that point!

Don't worry, just a placeholder :) Aleksander Stos 12:41, 13 November 2007 (CST)

--Warren Schudy 11:50, 18 November 2007 (CST) I added a todo list at the top of the page. Please feel free to edit it.

--Warren Schudy 12:14, 18 November 2007 (CST) Wikipedia uses "NP (complexity)" for the title. Is that a better name?

Claimed proof

There's a claimed proof for P not equal to NP.

PDF at author's page: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ He says this is a preliminary version, actual paper is a few weeks away.

Wow!!! Let us stay tuned; what else can I say? Boris Tsirelson 05:57, 9 August 2010 (UTC)
You were really fast to find this! You cannot expect us to already know if it is true, though. (If I remember correctly, there happened to be similar claims that turned out to be unfounded.) We are curious! --Peter Schmitt 09:42, 9 August 2010 (UTC)
An interesting and useful link [1]. --Peter Schmitt 23:57, 9 August 2010 (UTC)
A polymath wiki on this proof: [2] --Peter Schmitt 20:47, 11 August 2010 (UTC)
Discussion [3] Sandy Harris 23:10, 11 August 2010 (UTC)
Implications beyond mathematics: peer review and research funding. --Daniel Mietchen 23:22, 11 August 2010 (UTC)
Another interesting blog post, essentially betting $ 200 000 that it is wrong. --Peter Schmitt 23:51, 11 August 2010 (UTC)
An introduction to non-specialists by Richard J. Lipton, one of the specialists involved with verifying the proof. --Daniel Mietchen 12:23, 17 August 2010 (UTC)
Timeline. --Daniel Mietchen 23:22, 17 August 2010 (UTC)