Difference between revisions of "Talk:Computability and complexity"
ComplexZeta (talk | contribs) |
|||
| Line 2: | Line 2: | ||
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) | 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) | ||
Revision as of 14:10, 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)
