Talk:Computational complexity theory: Difference between revisions

Revision as of 03:22, 24 July 2009

Revision as of 12:12, 14 September 2009

Line 215:

"The fact that the P − NP problem has not been solved, and indeed has been shown to be unsolvable..." Is this right, and if so, reference? <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:J. Holden Caulfield|J. Holden Caulfield]] ([[User talk:J. Holden Caulfield|talk]] • [[Special:Contributions/J. Holden Caulfield|contribs]]) 17:34, 31 March 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

That would have been big news - it definitely isn't right so far.

But as a related question - in the section on P=NP, why is finding proofs of theorems in pure mathematics listed as something that could be done more efficiently if P=NP? By G&ouml;del's results, finding proofs of theorems in pure mathematics is an undecidable problem, and is therefore outside every complexity class, so I would have thought that P=NP would be basically irrelevant for it.

[[User:Easwaran|Easwaran]] ([[User talk:Easwaran|talk]]) 12:12, 14 September 2009 (UTC)

== Graph Theory ==