Complexity class

In computational complexity theory, a complexity class is a set of decision problems of related complexity.

A typical complexity class has a definition of the form:

the set of decision problems that can be solved by machine M using O(f(n)) of resource R (n is the size of the input)

For example, the class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time, while the class PSPACE is the set of decision problems that can be solved by a deterministic Turing machine in List of complexity classes