Компьютеры и труднодоступность -Computers and Intractability
 | |
| Автор | Майкл Р. Гарей и Дэвид С. Джонсон |
|---|---|
| Страна | Соединенные Штаты |
| Язык | английский |
| Серии | Серия книг по математическим наукам |
| Тема | Информатика |
| Жанр | Учебник |
| Издатель | В. Х. Фриман и компания |
Дата публикации |
1979 г. |
| Тип СМИ | Распечатать |
| Страницы | х + 338 |
| ISBN | 0-7167-1045-5 |
| OCLC | 247570676 |
| 519,4 | |
| Класс LC | QA76.6 .G35 |
В области информатики , а точнее теории вычислительной сложности , « Компьютеры и неразрешимость: руководство по теории NP-полноты» - это учебник Майкла Гэри и Дэвида С. Джонсона . Это была первая книга, посвященная исключительно теории NP-полноты и вычислительной сложности . В книге есть приложение, в котором содержится подробный сборник NP-полных задач (который был обновлен в последующих изданиях книги). В настоящее время книга в некоторых отношениях устарела, так как не охватывает более поздних разработок, таких как теорема PCP . Тем не менее, она все еще издается и считается классикой: в исследовании 2006 года поисковая система CiteSeer включила книгу в список наиболее цитируемых справочных материалов в литературе по информатике.
Открытые проблемы
В другом приложении к книге были представлены задачи, для которых не было известно, являются ли они NP-полными или в P (или ни то, ни другое). Проблемы (с их первоначальными названиями):
-
Изоморфизм графов
- Известно, что эта проблема находится в NP, но неизвестно, является ли она NP-полной.
- Гомеоморфизм подграфа (для фиксированного графа H )
- Род графа
- Завершение хордового графа
- Хроматический индекс
- Проблема четности связующего дерева
- Размер частичного заказа
- Планирование с ограничением приоритета для 3-х процессоров
- Эта проблема оставалась открытой по состоянию на 2016 год.
- Линейное программирование
- Полная унимодульность
-
Составное число
- Известно, что проверка составности выполняется в P, но сложность тесно связанной с ней проблемы целочисленной факторизации остается открытой.
-
Триангуляция минимальной длины
- Проблема 12 известна как NP-сложная, но неизвестно, относится ли она к NP.
Прием
Вскоре после выхода книга получила положительные отзывы авторитетных исследователей в области теоретической информатики.
В своем обзоре Рональд В. Бук рекомендует книгу «всем, кто хочет узнать о предмете NP-полноты», и он явно упоминает «чрезвычайно полезное» приложение с более чем 300 NP-трудными вычислительными задачами. Он заключает: «Информатике нужно больше книг, подобных этой».
Гарри Р. Льюис хвалит математическую прозу авторов: «Книга Гэри и Джонсона представляет собой исчерпывающее, ясное и практическое изложение NP-полноты. Во многих отношениях трудно представить себе лучшее рассмотрение предмета». Кроме того, он считает приложение «уникальным» и «отправной точкой в попытках показать, что новые проблемы являются NP-полными».
Спустя 23 года после выхода книги Лэнс Фортноу , главный редактор научного журнала Transactions on Computational Theory , заявляет: «Я считаю Гэри и Джонсона единственной самой важной книгой на книжной полке моего офиса. книга на их полках. [...] У Гэри и Джонсона есть лучшее введение в вычислительную сложность, которое я когда-либо видел ».