In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers).

The study of the relationships between complexity classes is a major area of research in theoretical computer science. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way:

L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆EXPSPACE

Where ⊆ denotes the subset relation. However, many relationships are not yet known; for example, one of the most famous open problems in computer science concerns whether P equals NP. The relationships between classes often answer questions about the fundamental nature of computation. The P versus NP problem, for instance, is directly related to questions of whether nondeterminism adds any computational power to computers and whether problems having solutions that can be quickly checked for correctness can also be quickly solved.

Complexity classes are sets of related computational problems. They are defined in terms of the computational difficulty of solving the problems contained within them with respect to particular computational resources like time or memory. More formally, the definition of a complexity class consists of three things: a type of computational problem, a model of computation, and a bounded computational resource. In particular, most complexity classes consist of decision problems that can be solved by a Turing machine with bounded time or space resources. For example, the complexity class P is defined as the set of decision problems that can be solved by a deterministic Turing machine in polynomial time.

Intuitively, a computational problem is just a question that can be solved by an algorithm. For example, "is the natural number ${\displaystyle n}$ prime?" is a computational problem. A computational problem is mathematically represented as the set of answers to the problem. In the primality example, the problem (call it ${\displaystyle {\texttt {PRIME}}}$) is represented by the set of all natural numbers that are prime: ${\displaystyle {\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ is prime}}\}}$. In the theory of computation, these answers are represented as strings; for example, in the primality example the natural numbers could be represented as strings of bits that represent binary numbers. For this reason, computational problems are often synonymously referred to as languages, since strings of bits represent formal languages (a concept borrowed from linguistics); for example, saying that the ${\displaystyle {\texttt {PRIME}}}$ problem is in the complexity class P is equivalent to saying that the language ${\displaystyle {\texttt {PRIME}}}$ is in P.

The most commonly analyzed problems in theoretical computer science are decision problems—the kinds of problems that can be posed as yes–no questions. The primality example above, for instance, is an example of a decision problem as it can be represented by the yes–no question "is the natural number ${\displaystyle n}$ prime". In terms of the theory of computation, a decision problem is represented as the set of input strings that a computer running a correct algorithm would answer "yes" to. In the primality example, ${\displaystyle {\texttt {PRIME}}}$ is the set of strings representing natural numbers that, when input into a computer running an algorithm that correctly tests for primality, the algorithm answers "yes, this number is prime". This "yes-no" format is often equivalently stated as "accept-reject"; that is, an algorithm "accepts" an input string if the answer to the decision problem is "yes" and "rejects" if the answer is "no".