Complexity class

In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Abstract machine - O

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 polynomial space. Some complexity classes are sets of function problems, such as FP.

Related Topics:
NP - Decision problem - Non-deterministic Turing machine - Polynomial time - PSPACE - Deterministic Turing machine - Polynomial space - Function problem - FP

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity.

Related Topics:
Mathematical logic - Descriptive complexity

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The Blum axioms can be used to define complexity classes without referring to concrete computational model.

Related Topics:
Blum axioms - Computational model

~ ~ ~ ~ ~ ~ ~ ~ ~ ~