|
|
| Line 1: |
Line 1: |
| − | == Classes ==
| + | Questions of '''computability''' and '''computational complexity''' are those which concern the limits of algorithms to solve certain types of problems in 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.) |
| − | Computability is divided into 2 compelxity classes, namely P and NP. For all problems in the P class, there exists a known algorithm to solve the problem in a reasonable amount of time. By this, it is meant that the algorithm will terminate within the time given by some polynomial <math>P(n)</math>, where <math>n</math> is the number of elements in the set being examined. In contrast, if a problem is NP, then there is no known algorithm to solve it in a reasonable amount of time.
| |
| | | | |
| − | | + | {{stub}} |
| − | == P ==
| |
| − | Within P, the computational complexity of problems is defined based on the highest degree term in the polynomial <math>P(n)</math>, and is represented using Big-Oh notation. For example if <math>P(n)</math> has degree <math>5</math>, then <math>P(n) \in O(n^5)</math>. More formally, if <math>f(x) \in O(g(x))</math>, then <math>\exists C \in \mathbb{R}</math> such that <math>|f(x)| <= C|g(x)|</math> as <math>x -> a</math>, for some <math>a</math> being specified. Thus, <math>f(x)</math> is bounded by <math>g(x)</math>.
| |
| − | | |
| − | == NP ==
| |
| − | NP problems take longer to solve and are not bounded by any polynomial. Examples include <math>f(n) \in O(2^n)</math>. A subset of NP problems are NP complete problems. They have the special property that the rearrangement of any one of them can yield another NP problem. Thus, if a polynomial time algorithm is found for any NP complete problem, then the conclusion will be that all NP problems are actually P problems, and therefore P = NP. This is currently one of the Millenium problems for which The Clay Mathematics Institute is offering a $1 million prize for a solution.
| |
Revision as of 13:39, 13 January 2007
Questions of computability and computational complexity are those which concern the limits of algorithms to solve certain types of problems in 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.)
This article is a stub. Help us out by expanding it.
