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 be the predicate for checking a solution on a deterministic Turing machine. Then, define:

An example are problems which are exponential in complexity, i.e., .

Menaka Lashitha Bandara 2005-04-18