Editing Computational complexity theory (section)

===Complexity measures===
For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the [[deterministic Turing machine]] is used. The time required by a deterministic Turing machine <math>M</math> on input <math>x</math> is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine <math>M</math> is said to operate within time <math>f(n)</math> if the time required by <math>M</math> on each input of length <math>n</math> is at most <math>f(n)</math>. A decision problem <math>A</math> can be solved in time <math>f(n)</math> if there exists a Turing machine operating in time <math>f(n)</math> that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time <math>f(n)</math> on a deterministic Turing machine is then denoted by [[DTIME]](<math>f(n)</math>).

Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any [[Complexity|complexity measure]] can be viewed as a computational resource. Complexity measures are very generally defined by the [[Blum complexity axioms]]. Other complexity measures used in complexity theory include [[communication complexity]], [[circuit complexity]], and [[decision tree complexity]].

The complexity of an algorithm is often expressed using [[big O notation]].