Computational complexity quantifies the resources required to perform a computational process or execute an algorithm. A computational complexity measure specifies a model of computation, a resource, and an input-size parameter, then records the resource usage as a function of that size. Common resources are computation time and memory, giving time and space complexity, respectively. Their growth is normally described using asymptotic notation, with separate best-case, average-case, and worst-case measures when these differ.
A complexity class groups computational problems according to a computational model and resource bound. For decision problems, the
class P consists of problems solvable in polynomial
time by a deterministic Turing machine, while
NP consists of problems solvable in polynomial
time by a nondeterministic Turing machine. Equivalently, proposed solutions to
NP problems can be verified in polynomial
time. The inclusion 
is known, but whether 
is the P versus NP problem.
An NP-hard problem is at least as hard as every
problem in NP, and an NP-complete problem
is both NP-hard and in NP. The classification of problems by such resource requirements
is studied in complexity theory (Du and Ko 2000).
