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

Учебное пособие.
М.: Факториал Пресс, 2006. — 128 с. — (Методы современной математики; Вып. 2)
ISBN: 5-88688-083-6
Тираж 1000 экз.Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М.В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности «Защита информации». Излагаются основные идеи и методы теории сложности вычислений.
Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.Оглавление:Часть первая. Модели вычисленийМашины Тьюринга
Неформальное введение
Модели Тьюринга
Многоленточные машины ТьюрингаВремя и память
Время и зона машины Тьюринга
Цена сокращения алфавита
Цена сокращения количества лентУниверсальные машины Тьюринга
MT, универсальная для класса С
Конструкция универсальной машины
Теоремы об иерархииМоделирование других языков
Схема моделирования других языков программирования машинами Тьюринга
Моделирование RAM
Моделирование булевых схемЧасть вторая. Сложностные классыКласс Р
Определение класса Р
Примеры: целочисленная арифметика
Примеры: арифметика остатков
Примеры: сложение и умножение матриц
Примеры: связность в графеКласс P/Poly
Распознавание языков последовательностями булевых схем
Континуальность класса P/Poly
Включение Р ⊂ P/PolyКласс NP
Определение класса NP
О проблеме Р ≠ NP
Примеры задач класса NPПримеры NP-полных задач
Сводимость ⩽ (Карп), NP-полнота
NP-полнота задачи SAT
NP-полнота задачи о клике
NP-трудность целочисленного ЛПКласс BPP
Вероятностные вычисления за полиномиальное время
Частотные распознаватели
Включение BPP ⊂ P/PolyВероятностный алгоритм распознавания простых чисел
Сведения из теории чисел
Извлечение корней
Вероятностный алгоритм
Верификация алгоритма
Оценка сложностиКонечные игры и класс РН
Конечные игры
Определение класса РН
Замкнутость относительно ∩, ∪ и (·)ᶜПолиномиальная иерархия
Классы полиномиальной иерархии
Структурные свойства полиномиальной иерархии
Пример
Включение ВРР ⊂ Σᵖ₂ ∩ Πᵖ₂Класс PSPACE
Класс PSPACE и игры с полиномиальным числом ходов
Моделирование игры
Моделирование на полиномиальной памяти
Игровая характеризация класса PSPACEПолные задачи для класса PSPACE и классов полиномиальной иерархии
Квантифицированные булевы формулы
Полные задачи для классов полиномиальной иерархии
Пример PSPACE-полной задачиСписок литературы
Предметный указатель