Talk:Computability and complexity

Revision as of 09:54, 8 January 2007 by ComplexZeta (talk | contribs)

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)