Talk:NP complexity class: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Boris Tsirelson
imported>Sandy Harris
(→‎Additions: soliciting editor comment)
 
(9 intermediate revisions by 3 users not shown)
Line 22: Line 22:


:Wow!!! Let us stay tuned; what else can I say? [[User:Boris Tsirelson|Boris Tsirelson]] 05:57, 9 August 2010 (UTC)
:Wow!!! Let us stay tuned; what else can I say? [[User:Boris Tsirelson|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! --[[User:Peter Schmitt|Peter Schmitt]] 09:42, 9 August 2010 (UTC)
::: An interesting and useful link [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm]. --[[User:Peter Schmitt|Peter Schmitt]] 23:57, 9 August 2010 (UTC)
::: A polymath wiki on this proof: [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper] --[[User:Peter Schmitt|Peter Schmitt]] 20:47, 11 August 2010 (UTC)
::: Discussion [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/] [[User:Sandy Harris|Sandy Harris]] 23:10, 11 August 2010 (UTC)
::::Implications beyond mathematics: [http://cameronneylon.net/blog/p-%E2%89%A0-np-and-the-future-of-peer-review/ peer review] and [http://www.psychologytoday.com/blog/nature-brain-and-culture/201008/p-np-and-is-academia-inhospitable-big-discoveries# research funding]. --[[User:Daniel Mietchen|Daniel Mietchen]] 23:22, 11 August 2010 (UTC)
::::: Another interesting [http://scottaaronson.com/blog/?p=456 blog] post, essentially betting $ 200 000 that it is wrong. --[[User:Peter Schmitt|Peter Schmitt]] 23:51, 11 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)
:::::::: An update by [http://rjlipton.wordpress.com/2010/08/15/the-p%E2%89%A0np-proof-is-one-week-old/ RJ Lipton]. --[[User:Peter Schmitt|Peter Schmitt]] 01:06, 18 August 2010 (UTC)
== Additions ==
I've been adding stuff under "Definition", trying for a simple explanation of the issue. Comment, especially from math or computer editors, solicited. [[User:Sandy Harris|Sandy Harris]] 11:08, 20 August 2010 (UTC)

Latest revision as of 05:08, 20 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)
An update by RJ Lipton. --Peter Schmitt 01:06, 18 August 2010 (UTC)

Additions

I've been adding stuff under "Definition", trying for a simple explanation of the issue. Comment, especially from math or computer editors, solicited. Sandy Harris 11:08, 20 August 2010 (UTC)

Retrieved from "https://citizendium.org/wiki/index.php?title=Talk:NP_complexity_class&oldid=334216"