Компьютеры и трудноразрешимость
 | |
| Автор | Майкл Р. Гэри и Дэвид С. Джонсон |
|---|---|
| Язык | Английский |
| Ряд | Серия книг по математическим наукам |
| Предмет | Информатика |
| Жанр | Учебник |
| Издатель | WH Freeman and Company |
Дата публикации | 1979 |
| Место публикации | Соединенные Штаты |
| Тип носителя | Распечатать |
| Страницы | х+338 |
| ISBN | 0-7167-1045-5 |
| ОКЛК | 247570676 |
| 519.4 | |
| Класс ЛК | QA76.6.G35 |
Компьютеры и трудноразрешимость: Руководство по теории NP-полноты — учебник Майкла Гэри и Дэвида С. Джонсона . [1] Это была первая книга исключительно по теории NP-полноты и вычислительной сложности . [2] В книге есть приложение, содержащее подробный сборник NP-полных задач (который был обновлен в более поздних изданиях книги). В настоящее время книга в некоторых отношениях устарела, поскольку она не охватывает более поздние разработки, такие как теорема PCP . Тем не менее, она до сих пор издается и считается классикой: в исследовании 2006 года поисковая система CiteSeer назвала книгу наиболее цитируемой ссылкой в литературе по информатике. [3]
Открытые проблемы [ править ]
В другом приложении к книге были представлены задачи, для которых было неизвестно, являются ли они NP-полными или в P (или ни тем, ни другим). Проблемы (с их первоначальными названиями):
- Изоморфизм графа
- Известно, что эта проблема существует в NP, но неизвестно, является ли она NP-полной.
- Гомеоморфизм подграфов (для фиксированного графа H )
- Род графа
- Завершение хордального графа
- Хроматический индекс [4]
- Проблема четности связующего дерева [5]
- Частичный размер заказа
- Планирование трех процессоров с ограничением приоритета
- По состоянию на 2016 год эта проблема все еще оставалась открытой. [6]
- Линейное программирование
- Полная унимодулярность [7]
- Составное число
- Известно, что проверка на составность осуществляется в P, но сложность тесно связанной проблемы факторизации целых чисел остается открытой.
- Триангуляция минимальной длины [8]
- Известно, что задача 12 NP-сложна, но неизвестно, входит ли она в NP.
Прием [ править ]
Вскоре после выхода книга получила положительные отзывы известных исследователей в области теоретической информатики.
В своем обзоре Рональд В. Бук рекомендует книгу «всем, кто хочет узнать о теме NP-полноты», и прямо упоминает «чрезвычайно полезное» приложение с более чем 300 NP-сложными вычислительными задачами. Он заключает: «Информатике нужно больше книг, подобных этой». [9]
Гарри Р. Льюис хвалит математическую прозу авторов: «Книга Гэри и Джонсона представляет собой тщательное, ясное и практическое изложение NP-полноты. Во многих отношениях трудно представить лучшую трактовку этого предмета». Кроме того, он считает приложение «уникальным» и «отправной точкой в попытках показать NP-полноту новых задач». [10]
Спустя двадцать три года после появления книги Лэнс Фортноу , главный редактор научного журнала Transactions on Computational Theory , заявляет: «Я считаю, что «Гэри и Джонсон» — единственная самая важная книга на книжной полке моего офиса. Каждый учёный-компьютерщик должен иметь эту книгу. книга также на их полках. [...] У Гэри и Джонсона лучшее введение в вычислительную сложность, которое я когда-либо видел». [11]
См. также [ править ]
Ссылки [ править ]
- ^ Гэри, MR ; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам. WH Freeman and Co. Сан-Франциско, Калифорния: ISBN 0-7167-1045-5 . МР 0519066 . 338 страниц. Скопируйте на archive.org.
- ^ Юрис Хартманис (1982). «Компьютеры и трудноразрешимые: Руководство по теории NP-полноты, рецензия на книгу». Обзор СИАМ . 24 (1): 90–91. дои : 10.1137/1024022 . JSTOR 2029450 .
- ^ «Самые цитируемые статьи в области компьютерных наук – сентябрь 2006 г. (CiteSeer.Continuity)» . Проверено 3 ноября 2007 г.
- ^ NP-полный: Холиер, Ян (ноябрь 1981 г.). «NP-полнота раскраски ребер». SIAM Journal по вычислительной технике . 10 (4): 718–720. дои : 10.1137/0210055 .
- ^ В П: Ловас, Л. Ловас, Л.; Соус, ВТ (ред.). Алгебраические методы в теории графов, том II (коллоквиум Сегед, 1978) . Colloquia Mathematica Societatis Янош Бойай, 25 лет. Северная Голландия. стр. 495–517.
- ^ ван Беверн, Рене; Бредерек, Роберт; Бюльто, Лоран; Комузевич, Кристиан; Талмон, Нимрод; Вегингер, Герхард Дж. (2016). «Задачи планирования с ограничением по приоритету, параметризованные шириной частичного заказа». DOOR 2016: Дискретная оптимизация и исследование операций . Конспекты лекций по информатике . Том. 9869. Шпрингер-Верлаг . стр. 105–120. arXiv : 1605.00901 . дои : 10.1007/978-3-319-44914-2_9 .
- ^ В П: Сеймур, П.Д. (июнь 1980 г.). «Разложение обычных матроидов» (PDF) . Журнал комбинаторной теории, серия B. 28 (3): 305–359. дои : 10.1016/0095-8956(80)90075-1 .
- ^ Является ли NP-сложным: Мюльцер, Вольфганг; Роте, Гюнтер (2008), «Триангуляция с минимальным весом NP-трудна», Журнал ACM , 55 (2), Art. 11, arXiv : cs.CG/0601002 , doi : 10.1145/1346330.1346336 , MR 2417038
- ^ Книга Рональда В. Обзор: Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты. Бюлл. амер. Математика. Соц. (NS), 3 (2), стр. 898–904, 1980 г.
- ^ Гарри Р. Льюис, Обзор: Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , Журнал символической логики , Vol. 48 (2), стр. 498–500, 1983 г.
- ^ Лэнс Фортноу , Великие книги: Компьютеры и трудноразрешимость: Руководство по теории NP-полноты Майкла Р. Гэри и Дэвида С. Джонсона. Блог о вычислительной сложности, 30 августа 2002 г.