Появление теории NP-полноты дало в руки инженерам и исследователям мощные рекомендации по методологии решения математических задач и инженерных проблем.

Теорема Кука и методика сведения задач привели к появлению в конце 1970-х годов нескольких сотен задач, про которые было доказано, что они являются NP-полными. (См, например, книгу [2]).

Выделим просто на основе здравого смысла в методике решения проблемы (обозначим ее ZZ) несколько этапов, интересующих нас.

1. Этап первичной формулировки. Инженер (или математик) сталкивается с некоторой пока неформализованной проблемой, которую нужно решить. Например, составление расписания занятий; составление графика (метода) разлива металла в заданный набор форм; прогноз затрат по данному бизнес-плану; составление наиболее интересного месячного путешествия по Европе и т.п.

2. Формулировка задачи. В данной неформализованной проблеме выделяется набор критичных параметров и целей (вопросов), на основе которых можно сформулировать задачу Z₀. Например, выделив условия и параметры расписания занятий, можно сформулировать конкретную проблему из теории расписаний; задав размеры форм и стоимостные характеристики деталей, из ни получаемых, можно прийти к задаче о рюкзаке; прогноз затрат по плану может привести к задаче линейного программирования; а путешествие по Европе к задаче коммивояжера.

3. Подбор алгоритма. Зная задачу, исследователь подбирает алгоритм ее решения. Здесь возможны. Например, следующие варианты. Вариант 3.1. В книгах, справочных материалах, Интернете алгоритм A(Z₀) найден. Вариант 3.2. В книгах, справочных материалах, Интернете алгоритм не найден. Исследователь самостоятельно строит некоторый алгоритм A(Z₀). Вариант 3.3. В книгах, справочных материалах, Интернете алгоритм не найден. Исследователь самостоятельно пытается строить некоторый алгоритм, но безуспешно.

4. Анализ алгоритма и возможная переформулировка задачи. В распоряжении исследователя есть алгоритм A(Z₀) и задача Z₀, а в случае варианта 3.3 только одна задача. Если параметры задачи и алгоритма укладываются в ресурсы исследователя, то процесс завершается. В противном случае исследователь может с помощью теории NP-полноты определить класс сложности задачи. Если задача полиномиально разрешима и полиномиален, то нужно позаботиться об увеличении вычислительных ресурсов. Это увеличение, как правило, вполне реально и легко оцениваемо. Далее – проблема решена. Если задача находится в классе NPC, то это означает, что десятки лет выдающиеся инженеры и математики безуспешно пытались ее решить. При этом увеличение ресурса ситуацию не спасет, поэтому совершенно естественно (и легко оправдываемо перед руководством) поступить одним из следующих способов. Вариант 4.1. Переформулировать требование к вопросу задачи. Например, искать не точное решение, а приближенное или допустить эвристические методы или методы направленного перебора (ветвей и границ) с элементами эвристик. Вариант 4.2. Из задачи Z₀ получить задачу Z₁. Возможно, неправильно оценены значимости целей и параметров на этапе первичной формулировки и можно немного изменить их соотношение. Это приведет к изменению формулировки задачи втором этапе. Например, вместо задачи коммивояжера можно получить задачу о кратчайшем остове, а вместо задачи ЦЛП задачу ЛП. Вариант 4.3. Из задачи Z₀ невозможно получить задачу Z₁. Анализ значимости целей и параметров на этапе первичной формулировки не позволяет на уровне самого исследователя изменить их соотношение. В этом случае инициативное исследование прекращается, если же задача является производственной, то для дальнейшего принятия решения привлекаются вышестоящие инстанции (и при разговоре с ними теория NP-полноты – решающий аргумент) в случае, если они обладают возможностью неограниченно увеличить ресурсы или кардинально поменять первичную формулировку задачи. А если не удается определить принадлежность задачи. Например, известно, что она лежит в NP, а про ее принадлежность к  P или NPC ничего нельзя сказать. Это наиболее тяжелый вопрос, на который проливает некоторый свет следующая теорема и комментарии к ней.

Обозначим NPI=NP\(NPC P). Если P NP, то класс NPI может быть непустым.

Теорема (Ладнер). Пусть B – некоторый рекурсивный язык, такой что B P (т.е. слова этого языка не распознаются за полиномиальное время на детерминированной машине Тьюринга). Тогда существует распознаваемый за полиномиальное время язык D P, такой, что язык A=D B не принадлежит P. При этом A B, а B A.

Доказательство этого утверждение можно найти в (Ladner R.E. On the structure of polynomialen time reducibility.- J. Assoc. Comput. Mach. 1975, v. 22, p. 155-171.)

Эта теорема имеет практическое применение, если P NP. Пусть B – задача «Гамильтонов цикл», тогда теорема утверждает, что найдется такой класс распознаваемых за полиномиальное время графов, что на этом классе графов задача «Гамильтонов цикл», не имея полиномильного алгоритма решения, в то же время не является NP-полной.

Если P NP, то теорема утверждает непустоту NPI класса и дает представление о его структуре. Он состоит из бесконечной совокупности классов эквивалентности языков, каждый из которых «чуть-чуть» сложнее другого. Кроме того в нем есть пары языков, ни один из которых полиномиально не сводится к другому!

Теорема Ладнера, к сожалению, не дает конструктивных методов построения «естественных» задач из класса NPI. Поэтому с 1971 года имеется достаточно интересная ситуация: существует очень небольшое, постоянно сужающееся множество естественных задач, про которые известно, что они не лежат ни в NPC, ни в P. В то же время не известна их принадлежность и к классу NPI. Почему сужающее? Потому, что постепенно задачи из этого множества куда-то определяются. Когда-то там лежала задача ЛП, но Л.Г.Хачиян доказал, что она лежит в P. Задача изоморфизм графа, простота числа (и ряд других из теории чисел) лежат там до сих пор.

10. Иерархия сложности

Классы NP и co-NP

Для любой Z задачи из NP можно сформулировать дополнительную задачу (язык) Z'. Если язык L_Z образуют все слова, являющиеся условием индивидуальных задач с ответом "да", то язык L_Z' образуют все слова, являющиеся условием индивидуальных задач с ответом "нет". Совокупность таких "дополнительных" задач и составляет класс co-NP. Аналогично для класса P может быть определен класс co-P.

Вообще говоря, дополнение множества слов, являющихся условиями индивидуальных задач с ответом "да", содержит два типа слов: слова, являющиеся кодами условиями индивидуальных задач с ответом "нет", и слова, не являющиеся условиями задач.

Предполагается, что последние можно отсеять с помощью каких-то вспомогательных "простых" процедур, например, синтаксических проверок и т.п.

Для любой задачи из класса P дополнение можно получить заменой заключительного состояния (q_no заменяем на q_yes и наоборот). Так как нет никакой угадывающей головки, то на любом корректно заданном условии задачи МТ остановится. Таким образом, мы автоматически получаем из МТ, решающей задачу Z, МТ для решения Z'. Поэтому классы P и co-P совпадают.

Пример. Рассмотрим задачу "Связность графа". Ее входом является неориентированный граф, а вопрос состоит в проверке его связности. Пусть граф G=(V,E) задан списками соседей вершин.

Рассмотрим следующий алгоритм. Берем пустое множество W.

1 шаг. На первом шаге включаем в него некоторую вершину v. Она считается помеченной, но не просмотренной. Переходим ко второму шагу.

2 шаг. Включаем в W всех соседей всех непросмотренных вершин. После этого только вновь включенные вершины считаются помеченными, но непросмотренными. Переходим к шагу 3.

3 шаг. Если W=V, то ответ "да". Если W¹V и непросмотренных вершин нет, то ответ "нет". В остальных случаях переходим к шагу 2.

Ясно, что шагов не более n. И на каждом шаге не более m проверок. Очевидно, что данный алгоритм решает как задачу с вопросом, связен ли G, так и задачу с вопросом, является ли G несвязным.

Для NP и co-NP ситуация иная. Например, обратная к задаче "гамильтонов цикл" задача состоит в ответе на вопрос: "Правда ли, что в данном графе нет гамильтонова цикла?" Как здесь может выглядеть подсказка? На сегодняшний день единственной возможной подсказкой представляется выписывание всех возможных гамильтоновых циклов и проверка их отсутствия в данном графе.

Но такой список циклов имеет экспоненциальную длину.

Поэтому вопрос о соотношении NP и co-NP является открытым.

Теорема 9.2. Если существует NP-полная задача Z такая, что ее дополнение лежит в NP, то

NP=co-NP.

Доказательство строится конструктивно с помощью композиции машин Тьюринга.

Пусть дополнение Z' некоторой NP-полной задачи Z лежит в NP. Покажем, что тогда дополнение W' любой задачи W лежит в NP. По определению полиномиальной сводимости функция f, осуществляющая эту сводимость, например, задачи W к задаче Z одновременно осуществляет полиномиальную сводимость задачи W' к задаче Z'. Функция f (одна МТ) вычисляется за полиномиальное время, проверка принадлежности Z' к NP (другая МТ, уже недетерминированная) тоже вычисляется за полиномиальное время. Поэтому проверка принадлежности W' к NP осуществляется путем последовательной комбинации этих двух машин, т.е. может быть проведена за полиномиальное время на недетерминированной МТ.

Классы P-SPACE и NP-SPACE.