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 -полными.

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

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