Полиномиальная сводимость и np-полные задачи

Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование так называемых NP-полных задач. NP-полные языки являются самыми «трудными» в классе NP. При этом трудность языков можно сравнивать, сводя один язык к другому.

Полиномиальная сводимость

Определение. Язык L₁ за полиномиальное время к языку L₂ (обозначение: L₁≤_pL₂ или L₁ L₂), если существует такая функция f : {0, 1}^*, вычислимая за полиномиальное время, что для любого слова х{0, 1}^* : xL₁  f(x)L₂ (х является индивидуальной задачей L₁ тогда и только тогда, когда f(x) является индивидуальной задачей L₂).

Функцию f называют сводящей функцией, а полиномиальный алгоритм A_f, вычисляющий функцию f, – сводящим алгоритмом.

 xL₁  f(x)L₂

 xL₁  f(x)L₂

Лемма 1. Если язык L₁{0, 1}^* сводится за полиномиальное время к языку L₂{0, 1}^* и L₂ принадлежит классу P, то L₁ также принадлежит классу Р (если L₁ L₂ и L₂P, то L₁Р).

Доказательство

1) L₁ L₂, следовательно, существует полиномиальный сводящий алгоритм А;

2) L₂P, следовательно, существует полиномиальный алгоритм распознавания языка L₂.

Возьмем произвольное слово хL₁ и с помощью алгоритма А сведем его к слову А(х)L₂, а затем определим, принимается или отвергается слово А(х) полиномиальным алгоритмом . Из определения полиномиальной сводимости следует, что слово А(х) допускается алгоритмом тогда и только тогда, когда слово x допускается алгоритмом, распознающим язык L₁. Таким образом, последовательное выполнение алгоритмов А и дает алгоритм распознавания языка L₁, и этот алгоритм полиномиален (сумма полиномов есть полином), т. е. L₁P.

Лемма 2. Отношение полиномиальной сводимости транзитивно (если L₁ L₂ и L₂ L₃, то L₁ L₃).

Определение. Языки L₁ и L₂ полиномиально эквивалентны, если сводятся друг к другу.

Понятие полиномиальной сводимости позволяет произвести классификацию языков по степени их «трудности». Запись L₁ L₂ можно интерпретировать так: сложность языка L₂ не более чем полиномиально превосходит сложность языка L₁. Наиболее трудные в этом смысле – NP-полные языки.

Определение. Язык L{0, 1}^* называется NP-полным:

1) если LNP;

2) L’ L для любого языка L’NP.

Обозначение класса NP-полных языков – NPC.

Лемма 3. Если языки L₁ и L₂ принадлежат классу NP, L₁ – это NP-полный язык и L₁ полиномиально сводится к L₂, то L₂ также NP-полный язык (если L₁NP, L₂NP, L₁NPC и L₁ L₂, то L₂NPС).

Доказательство. Так как L₂NP, то, согласно определению, достаточно доказать, что любой язык L’NP полиномиально сводится к языку L₂ (L’ L₂).

По условию леммы L₁NPC, следовательно, любой язык L’NP сводится к языку L₁ (L’NP: L’ L₁), а язык L₁ сводится к языку L₂ (по условию леммы L₁ L₂). По свойству транзитивности полиномиальной сводимости (лемма 2) L’NP: L’ L₁, L₁ L₂, следовательно, L’NР: L’ L₂, т.е язык L₂NPC.

Основное свойство NP-полных языков: если некоторый NP-полный язык разрешим за полиномиальное время, то классы P и NP эквивалентны (P=NP), т. е. если в классе NPС существует язык разрешимый за полиномиальное время, то все языки класса NPC разрешимы за полиномиальное время.

Доказательство. Пусть L – NP-полный язык, который одновременно оказался разрешимым за полиномиальное время (LNPC и LP). По определению NP-полного языка справедливо утверждение: любой язык L’, проверяемый за полиномиальное время, полиномиально сводится к языку L (L’NP: L’ L). Таким образом, L’NP: L’ L и LP, значит, по лемме 1 следует, что L’NP разрешима за полиномиальное время (L’NP: L’P), т. е. классы P и NP совпадают.