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. In a model whose elementary steps are operations on bits, the time measure is bit complexity, with input size measured in bits.
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).
Communication complexity measures the number of bits exchanged between parties that hold separate parts of an input. Local computation is unrestricted in this model, so communication is the resource being bounded (Kushilevitz and Nisan 1997).
