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