Крупский В.Н. Введение в сложность вычислений

М.: Факториал Пресс, 2006. - 128с.
Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности "Защита информации". Излагаются основные идеи и методы теории сложности вычислений.
Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.Оглавление:
Модели вычислений.
Машины Тьюринга.
Время и память.
Универсальные машины Тьюринга.
Моделирование других языков.
Сложностные классы.
Класс Р.
Класс Р/Poly.
Класс NР.
Примеры NР-полных задач.
Класс ВРР.
Распознавание простоты.
Конечные игры и класс РН.
Полиномиальная иерархия.
Класс PSPАСЕ.
РSРАСЕ-полные задачи.
Список литературы.
Предметный указатель.