Difference between revisions of "Computability and complexity"
Andrew Kim (talk | contribs) m (→P) |
|||
| Line 4: | Line 4: | ||
== P == | == 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>. | + | 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 == | ||
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. | 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 22:27, 6 January 2007
Classes
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 
, where 
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.
P
Within P, the computational complexity of problems is defined based on the highest degree term in the polynomial , and is represented using Big-Oh notation. For example if has degree 
, then 
. More formally, if 
, then 
such that 
as 
, for some 
being specified. Thus, 
is bounded by 
.
NP
NP problems take longer to solve and are not bounded by any polynomial. Examples include 
. 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.
