NP полиномиально разрешима, а если какая-либо задача из класса NP труднорешаема, то и задача о SAT так же труднорешаема. Таким образом, «задача SAT» - самая трудная в классе NP.
Наконец С. Кук предположил, что и другие задачи из класса NP могут быть самыми трудными в этом классе, аналогично задаче о выполнимости.
Вслед за Куком Р. Карп предположил, что многие хорошо известные задачи из комбинаторики, сформулированные в виде задачи о распознавании, так же трудны, как и задача о выполнимости.
Вопреки тому, как считают многие специалисты, что NP-полные задачи труднорешаемы, прогресс в отношении опровержения или подтверждения данного предположения весьма незначителен. Однако, несмотря на отсутствие доказательства того, что из NP-полноты следует труднорешаемость, NP-полнота задачи означает, что для решения ее за полиномиальное время требуется крупное открытие.
Так как все NP-полные задачи полиномиально сводимы друг к другу, то не имеет смысла решать бесконечное количество задач принадлежащих данному классу, а можно рассмотреть некоторое небольшое количество задач и изучить их решения.
Примеры NP-полных задач
- SAT
Условие:
Дан набор C={c1,c2,…,cm} дизъюнкций на конечном множестве переменных U, таких, что |ci| = 3, 1≤i≤m.
Вопрос:
Существует ли на U набор таких значений истинности, при котором выполняются все дизъюнкции из C?
- Вершинное покрытие (ВП)
Условие:
Дан граф G=(V, E) и положительное целое число K, K≤|V|.
Вопрос:
Имеется ли в графе G вершинное покрытие не более чем из K элементов, т.е. такое подмножество V' ⊆ V, что |V'|≤K и для каждого ребра {u,v} ∈E хотя бы одна из вершин u или принадлежит V' .
- Гамильтонов цикл (ГЦ)
Условие:
Дан граф G=(V, E).
Вопрос:
Верно ли, что граф G содержит гамильтонов цикл, т.е. такую последовательность <v1…vn> вершин графа G, что n=|V|, {vn,v1}∈E и {vi,vi+1}∈E для всех i, 1≤i≤n.
Для изучения нам нет смысла брать хитрые задачи, а достаточно рассмотреть одну из наиболее популярных задач-представителей данного класса – «задачу о коммивояжере».