Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mathinmoscow/listcur/Computability%20and%20Complexity.htm Дата изменения: Thu Nov 21 15:24:04 2013 Дата индексирования: Fri Feb 28 00:18:36 2014 Кодировка: Поисковые слова: moon

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. "; $programm = "

Decidable and enumerable sets. Computable functions.

Uncomputable functions and undecidable sets.

Rice-Uspensky’s theorem. Fixed point theorem.

Turing reductions and m-reductions, m-completeness. Relativization.

Turing machines. Thue and semi-Thue systems.

Computation time and space. Hierarchy theorems.

Uniform and nonuniform complexity. Boolean circuits.

Polynomial time, the class NP. Reductions, NP-completeness. The classes coNP, EXP, NEXP.

The class PSPACE. PSPACE-complete problems. Savitch’s theorem

Randomized algorithms. BPP. Primality testing.

Oracle separation of P and NP. Limits of diagonalization."; ?>