7.2. Complexity classes

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.