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

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

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

· существуют функции g(x) и f(x), вычисляемые за полиномиальное время;

· для любого входа x любого частного случая задачи Q значение g(x) является входом частного случая задачи R;

· для любого решения (выхода) y задачи R значение f(y) является решением задачи Q.

Таким образом, для решения одной задачи (в данном случае - Q) используется алгоритм другой задачи (R) (рис. 12).

Рис. 12. Полиномиальная сводимость программы Q к R

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

Определение.

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

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

Мы можем отождествить NP -полные задачи с "самыми трудными задачами из NP ". Если хотя бы одна NP -полная задача может быть решена за полиномиальное время, то и все NP -полные задачи труднорешаемы. Следовательно, любая NP -полная задача T обладает свойством: если P ¹ NP, то TÎ NP\P. Точнее, TÎ P тогда и только тогда, когда P = NP.

Первой задачей, для которой было доказано, что она является NP -полной, проблема о выполнимости:

Условие. Дана формула исчисления высказываний F, находящаяся в конъюнктивной нормальной форме.

Вопрос. Существует ли такое распределение истинностных значений высказывательных переменных, при которых формула F выполнима?

Теорема (теорема Кука). Задача о выполнимости является NP -полной [12, стр. 56-63].

Теперь, для того, чтобы доказать, что Q является NP -полной, мы каждый раз должны доказывать, что

· Q попадает в класс NP;

· задача о выполнимости полиномиально сводится к Q.

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

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

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

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

Умберто Эко "Маятник Фуко"