Difference between revisions of "Computability and complexity"
m |
|||
| Line 1: | Line 1: | ||
| − | Questions of '''computability''' and '''computational complexity''' are those which concern the limits of | + | Questions of '''computability''' and '''computational complexity''' are those which concern the limits of [[algorithm]]s to solve certain types of problems under certain constraints. Any algorithmic question can be placed into one or more [[complexity class]]es, 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 (complexity) | P]], [[NP]], [[decidability | undecidable]], etc.) |
| + | |||
| + | ==See Also== | ||
| + | * [[P versus NP]] | ||
{{stub}} | {{stub}} | ||
Latest revision as of 12:24, 6 July 2007
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.
