Учебное пособие.
M.: Факториал Пресс, 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-полной задачи
Список литературы
Предметный указатель
M.: Факториал Пресс, 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-полной задачи
Список литературы
Предметный указатель