Общая стратегия доказательства NP-полноты новых задач

В оставшейся части этой главы мы в основном будем заниматься изучением других NP-полных задач. В частности, мы обсудим другие разновидности сложных вычислительных задач и докажем, что некоторые представители этих категорий являются NP-полными.

Как упоминалось в начале главы, для этого есть чисто практическая причина: так как широко распространено мнение о том, что P ≠ NP, идентификация NP-полноты задачи может стать веским признаком того, что задача не может быть решена за полиномиальное время.

Основная стратегия доказательства NP-полноты новой задачи X выглядит примерно так:

1. Доказать, что X Ѯ NP.
2. Выбрать задачу Y, которая заведомо является NP-полной.
3. Доказать, что Y ≤P X.

Ранее было замечено, что многие сведения Y ≤P X состоят из преобразования заданного экземпляра Y в экземпляр X с тем же ответом. Для решения X используется одно обращение к «черному ящику». При использовании подобных сведений приведенная выше стратегия превращается в следующий план доказательства NP-полноты.

1. Доказать, что X Ѯ NP.
2. Выбрать задачу Y, которая заведомо является NP-полной.
3. Рассмотреть произвольный экземпляр sY задачи Y и показать, как построить за полиномиальное время экземпляр sX задачи X, обладающий следующими свойствами.
   • Если sY является экземпляром Y, на который дается ответ «да», то и sX является экземпляром X, на который дается ответ «да».

• Если sX является экземпляром X, на который дается ответ «да», то и sУ является экземпляром Y, на который дается ответ «да».

Другими словами, тем самым устанавливается, что sY и sX имеют одинаковый ответ.

Проводились исследования, направленные на изучение различий между сведениями с полиномиальным временем для специальной структуры (обращение к «черному ящику» с одним вопросом и буквальное использование полученного ответа) и более общей концепцией сведения с полиномиальным временем, при которых обращения к «черному ящику» могут производиться многократно.

(Более ограниченный вариант сведения называется сведением по Карпу, тогда как более общий вариант называется сведением по Куку или сведением по Тьюрингу с полиномиальным временем.) Здесь эти различия рассматриваться не будут.