The concept of complexity of Turing machines let us to define the complexity of tasks. As it is natural, the complexity of a task is equal to the complexity its solution.

**Definition 7.15.**

Let be a monotone increasing function. Then the set is the class of languages, which are solvable in time with deterministic Turing machines.

**Definition 7.16.**

Let be a monotone increasing function. Then the set is the class of languages, which are solvable on space with deterministic Turing machines.

**Definition 7.17.**

Let be a monotone increasing function. Then the set is the class of languages, which are solvable in time with nondeterministic Turing machines.

**Definition 7.18.**

Let be a monotone increasing function. Then the set is the class of languages, which are solvable on space with nondeterministic Turing machines.

One may recognize some simple relation between the different complexity classes.

**Theorem 7.19.**

Let and be two monotone increasing functions such that . Then .

**Proof**

Since , thus . This means that if a function satisfies , then holds, too. By definition, if , then there exists a Turing machine with time complexity such that . Hence , thus , i.e. . ✓

Similar results can be proven for the other complexity classes.

**Theorem 7.20.**

Let and be two monotone increasing functions such that . Then 1. ; 2. ; 3. .

**Proof**

The proof is similar to the proof of Theorem 7.19. ✓

**Theorem 7.21.**

Let be a monotone increasing. Then 1. ; 2. .

**Proof**

If , then by definition, for there exists a deterministic Turing machine with time complexity , such that . Since every deterministic Turing machine can be regarded as a nondeterministic one, thus with the same Turing machine the property holds, i.e. .

By similar arguments the statement can be proven. ✓

One may highlight some of the most important complexity classes (these classes does not contain transformation tasks, but in the examples they are cited, too):

1. : the class of the most simple tasks. One may notice, if some task has time complexity such that (i.e. grows strictly slower than ), then the Turing machine which solves the task even cannot read the complete input word. Some problem from this class: addition, search, word mirroring, negation, parity check and in general the recognition of regular languages. 2. : somewhat more difficult tasks as in the previous class. Some example: multiplication, division, matrix multiplication, polynomial multiplication, sorting, longest common subsequence search. 3. i.e. the class of tasks, which can be solved in polynomial time with deterministic Turing machine This class contains the relatively simple problems: searching the greatest common divisor, shortest path in a graph, minimal spanning tree search, computing the greatest flow in a graph. 4. i.e. the class of tasks, which can be solved in exponential time by a deterministic Turing machine. This class contains almost all problem, which can arise in practice. However, theoretically it is not true, since infinitely many of the algorithmically solvable problems are not in this class. 5. : the class of tasks, which can be solved by a nondeterministic Turing machine using linear space. 6. 7. : the class of tasks, which can be solved by a nondeterministic Turing machine in linear time. Surprisingly many problems are here. 8. the class of tasks, which can be solved by a nondeterministic Turing machine in polynomial time. One of the most important class in complexity theory.