This class of algorithms are the beginnings of what we call hard. NP does not mean Non-Polynomial. Essentially, NP algorithms run in P-time on a non-deterministic Turing machine. This is equivalent to saying that a solution can be checked in polynomial time.

Let $ check(s)$ be the predicate for checking a solution $ s = \Phi(i)$ on a deterministic Turing machine. Then, define:

    $\displaystyle NP = \left\{\Phi: s = \Phi (i), C(check (s)) \in O(n^p), p \in \mathbb{Z}\right\}$

An example are problems which are exponential in complexity, i.e., $ O(2^n)$.

Menaka Lashitha Bandara 2005-04-18