Recursive functions. Turing machines and their languages. The definition of complexity of algorithms. Time and space complexity. Classes complexity. Examples of polynomial algorithms. Reductions. P=NP question. NP-complete problems, examples. Classco NP. The spatial complexity. Savitch’s theorem. Classes L and NL. Class Pspace, winning strategies. Problems of enumeration. Probabilistic algorithms. Classes BPP, RP and coRP. De-randomization. Small sampling areas. Approximation algorithms. Class NPO. A part of the subject is conducted through independent study research.