NP

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:

$$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)$.