Computability and complexity

Revision as of 12:24, 6 July 2007 by JBL (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Questions of computability and computational complexity are those which concern the limits of algorithms to solve certain types of problems under certain constraints. Any algorithmic question can be placed into one or more complexity classes, depending on a number of factors such as the speed of the fastest possible solution under a given model of computation. This article is for background and definitions of such models of computation (Turing machines, finite automata, or the like) and associated complexity classes ( P, NP, undecidable, etc.)

See Also

This article is a stub. Help us out by expanding it.