Talk:NP complexity class

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

Unused subpages
Unused subpages: - External Links - Works - Discography - Filmography - Catalogs - Timelines - Gallery - Audio - Video - Code - Tutorials - Student Level - Signed Articles - Function - Addendum - Debate Guide - Advanced - Recipes - Citable Version

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)

Talk:NP complexity class

Claimed proof

Navigation menu

Search