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

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

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

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
  • Дополнительные домашние задания

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

Список исправлений незначительных ошибок

Веб-страница издателя

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