NP-трудные и NP-полные задачи

Определениe: Задача Q полиномиально сводится к задаче Rтогда и только тогда, когда выполнены условия:

1) Существуют функции и , вычисляемые за полиномиальное время ;

2) Для любого входа и для любого частного случая задачи Qзначение - вход частного случая задачи R;

3) Для любого решения (выхода) задачи Rзначение - решение задачи Q:

Определение: Если одновременно задача Q полиномиально сводится к задаче R и задача R полиномиально сводится к задаче Q, то задачи Qи R полиномиально эквивалентны.

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

Другими словами, задача Т является NP-трудной,если она по крайней мере так сложна, как любая задача в NP.

NP-полные задачи – это самые трудные из NP.

Любая NP-полная задача Т принадлежит NP\Р.Точнее, задача Т принадлежит к классу Р тогда и только тогда, когда Р=NP.

Теорема Кука (задача о выполнимости является NP-полной): F – формула из теории L (ИВ – исчисление высказываний) представлена в КНФ. Существует ли такое распределение истинностных значений высказывательных переменных, при которых формула F выполнима?

Доказательство: Обозначим задачу распределения истинностных значений высказывательных переменных, при которых формула F выполнима, через задачу Т. Задача о выполнимости Т полиномиально сводится к любой NP-трудной задаче,принадлежащей к классуNP,то есть она является NP-полной.

К настоящему времени установлена NP-полнота большого числа задач. Выше были перечислены некоторые задачи, которые не попадают ни в класс Р, ни в класс Е. Все они являются NP-полными.

Проблема состоит в следующем: можем ли мы надеяться, что какая-либо из этих задач имеет полиномиальную сложность?

По-видимому, ответ будет неудовлетворительным. Очень важным аргументом для такого вывода служит тот факт, что все задачи эквивалентны по сложности – стоит нам найти какой-то полиномиальный алгоритм для одной из этих задач, то все эти задачи становятся полиномиально сложны.