Difference between revisions of "Talk:Computability and complexity"

 
m (stub it)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
This is wrong -- there are a wide variety of computational complexity classes other than P and NP.  The content should probably be separated into articles, one for P, one for NP, and any others for any other computational classes anyone cares to write an article about, with this page serving as background and links to more specific articles.  --[[User:JBL|JBL]] 17:41, 4 November 2006 (EST)
 
This is wrong -- there are a wide variety of computational complexity classes other than P and NP.  The content should probably be separated into articles, one for P, one for NP, and any others for any other computational classes anyone cares to write an article about, with this page serving as background and links to more specific articles.  --[[User:JBL|JBL]] 17:41, 4 November 2006 (EST)
 +
 +
Furthermore, the description of NP is incorrect -- NP problems are problems that can be solved by a nondeterministic Turing machine in polynomial time. Alternatively, the solution of an NP problem can be verified in polynomial time. --[[User:ComplexZeta|ComplexZeta]] 09:54, 8 January 2007 (EST)
 +
 +
I'm inclined just to delete this page and wait for someone to come along and write a correct one -- what do you think?  --[[User:JBL|JBL]] 14:10, 8 January 2007 (EST)
 +
 +
If you delete it, it won't be listed in the Random Page pages and so people hunting for an article to write won't stumble across this information. Maybe shorten it and stub it?--[[User:Solafidefarms|solafidefarms]] 22:12, 8 January 2007 (EST)

Latest revision as of 22:12, 8 January 2007

This is wrong -- there are a wide variety of computational complexity classes other than P and NP. The content should probably be separated into articles, one for P, one for NP, and any others for any other computational classes anyone cares to write an article about, with this page serving as background and links to more specific articles. --JBL 17:41, 4 November 2006 (EST)

Furthermore, the description of NP is incorrect -- NP problems are problems that can be solved by a nondeterministic Turing machine in polynomial time. Alternatively, the solution of an NP problem can be verified in polynomial time. --ComplexZeta 09:54, 8 January 2007 (EST)

I'm inclined just to delete this page and wait for someone to come along and write a correct one -- what do you think? --JBL 14:10, 8 January 2007 (EST)

If you delete it, it won't be listed in the Random Page pages and so people hunting for an article to write won't stumble across this information. Maybe shorten it and stub it?--solafidefarms 22:12, 8 January 2007 (EST)