Computability and Complexity

A problem could be algorithmically unsolvable. On the other hand, a theoretically solvable problem could require so much time to be solved that from the practical viewpoint it does not differ from an unsolvable one. Only if a fast algorithm exists, can the problem be regarded as practically solvable, or feasible. Sometimes it is hard to make a distinction between these possibilities, but the theory of computation helps us in many important cases. We will try to explain the main results of this theory (computational models, undecidability, complexity classes P and NP, randomized algorithms, etc.)


Curriculum:

  1. Decidable and enumerable sets. Computable functions.
  2. Uncomputable functions and undecidable sets.
  3. Rice-Uspensky’s theorem. Fixed point theorem.
  4. Turing reductions and m-reductions, m-completeness. Relativization.
  5. Turing machines. Thue and semi-Thue systems.
  6. Computation time and space. Hierarchy theorems.
  7. Uniform and nonuniform complexity. Boolean circuits.
  8. Polynomial time, the class NP. Reductions, NP-completeness. The classes coNP, EXP, NEXP.
  9. The class PSPACE. PSPACE-complete problems. Savitch’s theorem
  10. Randomized algorithms. BPP. Primality testing.
  11. Oracle separation of P and NP. Limits of diagonalization.

Textbooks

  • A.Shen, N.K. Vereshchagin, Computable functions, Providence, R.I.: Amer. Math. Soc., 2003.
  • Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press.
  • M. Sipser, Introduction to the theory of computation, 2-nd ed., International edition.-N.-Y.: Thomson Course Technology, 2006.