Компьютеры и несговорчивость
-
Обзор книги «Компьютеры и неразрешимость»
- Книга Майкла Гэри и Дэвида С. Джонсона является первым учебником по теории NP-полноты.
- В книге содержится приложение с перечнем NP-полных задач, которое было обновлено в последующих изданиях.
- Несмотря на устаревание из-за отсутствия более поздних разработок, книга остается классической и цитируемой в области компьютерных наук.
-
Открытые проблемы в теории NP-полноты
- В книге представлены задачи, для которых неизвестно, являются ли они NP-полными или нет.
- Среди этих задач есть проблемы изоморфизма графов, гомоморфизма подграфа, родства графа и другие.
- Некоторые из этих задач, такие как проблема трехпроцессорного планирования с ограниченным приоритетом, остаются открытыми по состоянию на 2016 год.
-
Прием и значимость книги
- Книга получила положительные отзывы от известных исследователей и была рекомендована для ознакомления с темой NP-полноты.
- Приложение к книге считается уникальным и важным для демонстрации NP-полноты новых задач.
- Книга считается важным введением в вычислительную сложность и рекомендуется специалистами по информатике.
Полный текст статьи: