Теория вычислимости и сложности

Ссылка на источник: http://cs-www.bu.edu/faculty/homer/complexitybook-vol2-webpg.html

Теория вычислимости и сложности
Второе издание
Стивен Гомер и Алан Л. Сельман
Springer Verlag Нью-Йорк, 2011
ISBN 978-1461406815

Это пересмотренное и расширенное издание теории вычислимости и сложности содержит основные материалы, которые являются основными знаниями в теории вычислений. Книга является отдельной, с предварительной главой, описывающей ключевые математические понятия и обозначения, и последующими главами, переходящими от качественных аспектов классической теории вычислимости к количественным аспектам теории сложности. Выделенные главы о неразрешимости, NP-полноте и относительной вычислимости завершают первое издание, в котором рассматриваются ограничения вычислимости и различия между выполнимым и неразрешимым.

Существенно новый контент во втором издании включает в себя:

* глава о неравномерности изучения булевых цепей, советов и важного результата Карпа-Липтона

* определения и свойства фундаментальных вероятностных классов сложности

* исследование переменных машин Тьюринга и классов однородных цепей

* введение в подсчет классов, включая результаты Valiant и Vazirani и Toda

* тщательная обработка доказательства того, что IP идентичен PSPACE

Темы и особенности:

* Краткие, сфокусированные материалы охватывают наиболее фундаментальные понятия и результаты в области современной теории сложности, включая теорию NP-полноты, NP-твердости, полиномиальной иерархии и полных задач для других классов сложности.

* Содержит информацию, которая в противном случае существует только в исследовательской литературе, и представляет ее в унифицированном, упрощенном виде; например, о дополнениях классов сложности, задачах поиска и промежуточных задачах в NP, неравномерной и параллельной теории сложности, вероятностных классах сложности, счетных классах и интерактивных системах доказательства.

* Предоставляет ключевую математическую справочную информацию, включая разделы по логике и теории чисел и алгебре

* Поддерживается многочисленными упражнениями и дополнительными задачами для подкрепления и самостоятельных занятий.

С его доступностью и хорошо продуманной организацией, этот текст / ссылка является отличным ресурсом и руководством для тех, кто хочет получить прочную основу в теории вычислений. Начинающие выпускники, продвинутые магистранты и специалисты, занимающиеся теоретической информатикой, теорией сложности и вычислимостью, найдут книгу важным и практическим инструментом обучения.

Оглавление

  1. ПРЕДВАРИТЕЛЬНЫЕ

Слова и языки
K-adic Презентация
Частичные функции
Диаграммы
Логика высказываний
Мощность
Элементарная алгебра

2. ВВЕДЕНИЕ В ВЫЧИСЛИТЕЛЬНОСТЬ

Машины Тьюринга
Концепции машины Тьюринга
Вариации машин Тьюринга
Церковный тезис
НВЧ

3. НЕРАЗРЕШИМОСТЬ

Решение проблем
Неразрешимые проблемы
Функции сопряжения
Вычислимо перечислимые множества
Задача остановки, сокращения и полные наборы
S-m-n Теорема
Теорема о рекурсии
Теорема Райса
Сокращения Тьюринга и машины Тьюринга с оракулом
Теорема о рекурсии, продолжение
Рекомендации
Дополнительные домашние задания

4. ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ

Классы сложности и меры сложности
Предпосылки

5. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ТЕОРИИ СЛОЖНОСТИ

Линейное сжатие и ускорение
Конструируемые функции
Сокращение ленты
Отношения включения
– Отношения между стандартными классами
Результаты разделения
Методы перевода и отступы
Отношения между стандартными классами – продолжение
– Дополнения к классам сложности: теорема Иммермана-Селепченого
Дополнительные домашние задания

6. НОНДЕТЕРМИНИЗМ И NP-Полнота

Характеристики NP
Класс P
Перечисления
NP-полнота
Теорема Кука-Левина
Больше NP-полных задач
Дополнительные домашние задания

7. ОТНОСИТЕЛЬНАЯ ВЫЧИСЛИМОСТЬ

NP-Твердость
Проблемы с поиском
Структура NP
– Составное число и граф Изоморфизм
– Отражение
Полиномиальная Иерархия
Полные задачи для других классов сложности
Дополнительные домашние задания

8. НЕУНИФОРМНАЯ СЛОЖНОСТЬ

Полиномиальный размер семейства цепей
– Совет Классы
Низкие и Высокие Иерархии

9. ПАРАЛЛЕЛЬНОСТЬ

Чередующиеся машины Тьюринга
Единые Семьи Цепей
Сильно распараллеливаемые проблемы
Условия однородности
Чередующиеся машины Тьюринга

10. КЛАССЫ ВЕРОЯТНОЙ СЛОЖНОСТИ

Класс PP
Класс RP
– Класс ZPP
Класс BPP
Случайно выбранные хэш-функции
– Операторы
Проблема изоморфизма графов
Дополнительные домашние задания

11. ВВЕДЕНИЕ В СЧЕТНЫЕ КЛАССЫ

Уникальная удовлетворенность
Теорема Тоды
– Результаты по BPP и Паритету P
Дополнительные домашние задания

12. ИНТЕРАКТИВНЫЕ ДОКАЗАТЕЛЬНЫЕ СИСТЕМЫ

Формальная модель
Проблема неизоморфизма графов
Артур-Мерлин Игры
IP включен в PSPACE
PSPACE включен в IP
Дополнительные домашние задания

Leave a Reply

Your email address will not be published. Required fields are marked *