Editing Computational complexity theory (section)

===Defining complexity classes===
A '''complexity class''' is a set of problems of related complexity. Simpler complexity classes are defined by the following factors:
* The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on [[function problem]]s, [[counting problem (complexity)|counting problem]]s, [[optimization problem]]s, [[promise problem]]s, etc.
* The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, [[Boolean circuit]]s, [[quantum Turing machine]]s, [[monotone circuit]]s, etc.
* The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.

Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following:

:The set of decision problems solvable by a deterministic Turing machine within time <math>f(n)</math>. (This complexity class is known as DTIME(<math>f(n)</math>).)

But bounding the computation time above by some concrete function <math>f(n)</math> often yields complexity classes that depend on the chosen machine model. For instance, the language <math>\{xx \mid x \text{ is any binary string}\}</math> can be solved in [[linear time]] on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, [[Cobham's thesis|Cobham-Edmonds thesis]] states that "the time complexities in any two reasonable and general models of computation are polynomially related" {{Harv|Goldreich|2008|loc=Chapter 1.2}}. This forms the basis for the complexity class [[P (complexity)|P]], which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is [[FP (complexity)|FP]].