stringtranslate.com

Компьютеры и неподатливость

Computers and Intractability: A Guide to the Theory of NP-Completeness — учебник Майкла Гэри и Дэвида С. Джонсона . [1] Это была первая книга, посвященная исключительно теории NP-полноты и вычислительной неразрешимости . [2] В книге есть приложение, содержащее полный сборник NP-полных задач (который был обновлен в более поздних изданиях книги). В настоящее время книга в некоторых отношениях устарела, поскольку не охватывает более поздние разработки, такие как теорема PCP . Тем не менее, она все еще издается и считается классикой: в исследовании 2006 года поисковая система CiteSeer включила эту книгу в список наиболее цитируемых источников в литературе по информатике. [3]

Открытые проблемы

В другом приложении к книге были представлены задачи, для которых не было известно, были ли они NP-полными или P (или ни тем, ни другим). Задачи (с их оригинальными названиями) таковы:

  1. Изоморфизм графов
    Известно, что эта задача относится к классу NP, но неизвестно, является ли она NP-полной.
  2. Гомеоморфизм подграфа (для фиксированного графа H )
  3. Граф род
  4. Завершение хордового графика
  5. Хроматический индекс [4]
  6. Проблема четности связующего дерева [5]
  7. Измерение частичного порядка
  8. Планирование с ограничением приоритета на 3 процессора
    Эта проблема оставалась открытой по состоянию на 2016 год. [6]
  9. Линейное программирование
  10. Полная унимодулярность [7]
  11. Составное число
    Известно, что проверка на составность выполняется в P, но сложность тесно связанной задачи факторизации целых чисел остается открытой.
  12. Минимальная длина триангуляции [8]
    Известно, что задача 12 относится к NP-трудным задачам, но неизвестно, входит ли она в NP.

Прием

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

В своем обзоре Рональд В. Бук рекомендует книгу «всем, кто хочет узнать о предмете NP-полноты», и он явно упоминает «чрезвычайно полезное» приложение с более чем 300 NP-трудными вычислительными задачами. Он заключает: «Компьютерной науке нужно больше книг, подобных этой». [9]

Гарри Р. Льюис хвалит математическую прозу авторов: «Книга Гэри и Джонсона представляет собой тщательное, ясное и практическое изложение NP-полноты. Во многих отношениях трудно представить себе лучшую трактовку предмета». Также он считает приложение «уникальным» и «отправной точкой в ​​попытках показать, что новые задачи являются NP-полными». [10]

Спустя двадцать три года после выхода книги Лэнс Фортноу , главный редактор научного журнала Transactions on Computational Theory , утверждает: «Я считаю, что Garey and Johnson — самая важная книга на книжной полке моего офиса. Каждый специалист по информатике также должен иметь эту книгу на своей полке. [...] Garey and Johnson — лучшее введение в вычислительную сложность, которое я когда-либо видел». [11]

Смотрите также

Ссылки

  1. ^ Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ред.). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам. Сан-Франциско, Калифорния: W. H. Freeman and Co. ISBN 0-7167-1045-5. МР  0519066.338 страниц. Копия на archive.org
  2. ^ Юрис Хартманис (1982). «Вычислители и неразрешимость: руководство по теории NP-полноты», рецензия на книгу. SIAM Review . 24 (1): 90–91. doi :10.1137/1024022. JSTOR  2029450.
  3. ^ "Самые цитируемые статьи в Computer Science - сентябрь 2006 (CiteSeer.Continuity)" . Получено 2007-11-03 .
  4. ^ NP-полнота: Холиер, Ян (ноябрь 1981 г.). «NP-полнота раскраски рёбер». SIAM Journal on Computing . 10 (4): 718–720. doi :10.1137/0210055.
  5. ^ В P: Ловас, Л. Ловас, Л.; Сос, В.Т. (ред.). Алгебраические методы в теории графов, том II (коллоквиум Сегед, 1978) . Colloquia Mathematica Societatis Янош Бойай, 25 лет. Северная Голландия. стр. 495–517.
  6. ^ Ван Беверн, Рене; Бредерек, Роберт; Булто, Лоран; Комусевич, Кристиан; Талмон, Нимрод; Вёгингер, Герхард Дж. (2016). «Задачи планирования с ограничениями по приоритету, параметризованные частичной шириной порядка». DOOR 2016: Дискретная оптимизация и исследование операций . Конспект лекций по информатике . Том 9869. Springer-Verlag . С. 105–120. arXiv : 1605.00901 . doi :10.1007/978-3-319-44914-2_9.
  7. ^ В P: Seymour, PD (июнь 1980). "Разложение регулярных матроидов" (PDF) . Журнал комбинаторной теории, серия B . 28 (3): 305–359. doi : 10.1016/0095-8956(80)90075-1 .
  8. ^ Является ли NP-трудной: Мульцер, Вольфганг; Роте, Гюнтер (2008), "Триангуляция с минимальным весом является NP-трудной", Журнал ACM , 55 (2), Статья 11, arXiv : cs.CG/0601002 , doi :10.1145/1346330.1346336, MR  2417038
  9. ^ Рональд В. Обзор книги: Компьютеры и неподатливость: Руководство по теории NP-полноты Bull. Amer. Math. Soc. (NS), 3 (2), стр. 898–904, 1980
  10. ^ Гарри Р. Льюис, Обзор: Компьютеры и неподатливость: Руководство по теории NP-полноты, Журнал символической логики , т. 48 (2), стр. 498–500, 1983
  11. ^ Лэнс Фортноу , Великие книги: Компьютеры и неразрешимость: Руководство по теории NP-полноты Майкла Р. Гэри и Дэвида С. Джонсона. Блог о вычислительной сложности, 30 августа 2002 г.