Оригинал статьи доступен на bu.edu.

Второе издание

Стивен Гомер и Алан Селман

Springer Verlag New York, 2011

ISBN 978-1461406815

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

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

  • Глава о неоднородности изучения булевых схем, классы советов и важный результат Карпа-Липтона
  • Определения и свойства фундаментальных классов вероятностной сложности
  • Изучение чередующихся классов машин Тьюринга и однородных цепочек
  • Введение в подсчет классов, включая результаты Валианта и Вазирани и Тода
  • Тщательная обработка доказательств того, что IP идентична PSPACE

Темы и функции:

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

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

Содержание

  1. Преамбула
    • Слова и языки
    • К-адическая репрезентация
    • Частичная функция
    • Диаграммы
    • Пропозициональная логика
    • Кардинальность
    • Элементарная алгебра
  1. Введение в вычисляемость
    • Машина Тьюринга
    • Концепции машины Тьюринга
    • Вариации машин Тьюринга
    • Тезисы церкви
    • RAM
  1. Неразрешимость
    • Проблемы решения
    • Неразрешимые проблемы
    • Сопряжение функций
    • Вычислимые счетные множества
    • Проблема остановки, сокращения и полные наборы
    • Теорема S-М-Н
    • Теорема Рекурсии
    • Теорема Райса
    • Сокращения Тьюринга и машины Oracle Тьюринга
    • Теорема рекурсии, Продолжение
    • Ссылки на литературу
    • Дополнительные домашние задание
  1. Введение в теорию сложности
    • Классы сложности и меры сложности
    • Необходимые компоненты
  1. Основные результаты теории сложности
    • Линейное сжатие и ускорение
    • Конструктивные функции
    • Уменьшение ленты
    • Отношения включения
    • Отношения между стандартными классами
    • Результаты разделения
    • Техника перевода и отступы
    • Отношения между стандартными классами – продолжение
    • Дополнения классов сложности: Теорема Иммермана-Селепцени
    • Дополнительные домашние задания
  1. Недетерминизм и NP-полнота
    • Характеристика NP
    • Класс P
    • Перечисления
    • NP-полнота
    • Теорема Кука-Левина
    • Больше NP-полных задач
    • Дополнительные домашние задания
  1. Относительная вычислимость
    • NP-трудность
    • Поиск проблем
    • Структура NP
    • Составное число и изоморфизм графов
    • Отражение
    • Полиномиальная bерархия
    • Завершите задачи для других классов сложности
    • Дополнительные домашние задания
  1. Неоднородная сложность
  • Полиномиальные размерные семейства схем
  • Классы советов
  • Низкие и высокие иерархии
  1. Параллелизм
    • Чередующие машины Тьюринга
    • Равномерные семьи цепочек
    • Высоко-распараллеливаемые проблемы
    • Условия единообразия
    • Чередующие машины Тьюринга
  1. Вероятностные классы сложности
    • Класс PP
    • Класс RP
    • ZPP класс
    • Класс BPP
    • Случайно выбранные хэш-функции
    • Операторы
    • Проблема изоморфизма графов
    • Дополнительные домашние задания
  1. Введение в классы подсчета
    • Уникальная выполнимость
    • Теорема Тода
    • Результаты по BPP и четности Р
    • Дополнительные домашние задания
  1. Интерактивные системы доказательств
    • Формальная модель
    • График Не-Изоморфической проблемы
    • Игры Артура-Мерлина
    • IP включен в PSPACE
    • PSPACE включен в IP
    • Дополнительные домашние задания

Важные ссылки: