Computability and complexity

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 $P(n)$ , where $n$ 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 $P(n)$ , and is represented using Big-Oh notation. For example if $P(n)$ has degree $5$ , then $P(n) \in O(n^5)$ . More formally, if $f(x) \in O(g(x))$ , then $\exists C \in \mathbb{R}$ such that $|f(x)| <= C|g(x)|$ as $x -> a$ , for some $a$ being specified. Thus, $f(x)$ is bounded by $g(x)$ .

NP

NP problems take longer to solve and are not bounded by any polynomial. Examples include $f(n) \in O(2^n)$ . 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.

Page

Toolbox

Search

Computability and complexity

Classes

P

NP