15. Взаимоотношения между класами p и np.

Вопрос об этом взаимоотношении играет фундаментальную роль в теории NP полных задач. Одно соотношение известно точно . Действительно, если задача разрешима полиномиальным детерминированным алгоритмом, то недетерминированный алгоритм может быть получен следующим образом: в качестве указанной структурыS возьмём пустую структуру, а на стадии проверки используем полиномиальный детерминированный алгоритм решения задачи.

Имеется много причин считать, что написанное неравенство является строгим, т.е. класс P не совпадает с NP. Недетерминированные полиномиальные алгоритмы являются более мощными, чем полиномиальные детерминированные алгоритмы, и неизвестны общие методы превращения первого в последний. Самый сильный из известных в настоящее время результатов состоит в следующем.

Теорема 1:

Если , то существует такой полиномp, что П может быть решена детерминированным алгоритмом с временной сложностью O(2^p(n)).

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

Пусть A полиномиальный недетерминированный алгоритм решения задачи П. q(n) – полином, ограничивающий время работы алгоритма A. Не теряя общности можно сказать, что q может быть вычислен за полиномиальное время. Этого можно добиться, взяв, например, при достаточно большихc₁ и c₂. По определению класса NP для каждого входа длины n найдётся некоторое слово-догадка длины не более чем q(n). При этом алгоритм A на стадии проверки даст ответ “да” не более чем за q(n) шагов. Таким образом, общее число догадок которое необходимо рассмотреть, не превосходит k^q(n), где k – количество символов в собственном алфавите V МТ. Теперь можно детерминированным образом выяснить, имеет ли алгоритм A на заданном входе длины n принимающее вычисление. Для этого достаточно на каждой из k^q(n) догадок запустить детерминированную стадию проверки алгоритма A. При этом мы позволим алгоритму работать либо до момента, когда он остановится, либо когда он сделает q(n) шагов. Описанный моделирующий алгоритм выдаёт ответ “да” если ему встретится слово-догадка, приводящее к принимающему вычислению с временем работы не более чем q(n), иначе ответом будет “нет”. Этот алгоритм является детерминированным решением задачи П и его временная сложность будет равна q(n)k^q(n). При подходящем выборе полинома p(n), это величина не превосходит O(2^p(n)) ч.т.д.

Большое количество задач, типа КОММИВОЯЖЁР или ИЗОМОРФИЗМ ПОДГРАФУ, принадлежат NP, и, несмотря на длительные рассмотрения этих задач большим количеством исследователей, полиномиального алгоритма до сих пор не найдено, поэтому широко распространено мнение, что NPP. Хотя доказательство этого факта до сих пор отсутствует, со значительной долей уверенности можно предполагать, что класс NP имеет структуру:

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

Будем говорить, что имеет место полиномиальная сводимость языка к языку, если существует функцияудовлетворяет двум условиям:

1. Существует ДМТ-программа, вычисляющая функцию с временной сложностью, ограниченной полиномом.

2. Для любого ,.

Полиномиальная сводимость обозначается значком «». L₁L₂.

Лемма 1.

Если L₁L₂, то ( также эквивалентно высказывание).

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

Пусть и– алфавиты языковL₁ и L₂, а функция осуществляет полиномиальную сводимость. ПустьM – ДМТ-программа вычисления f, M₂ – полиномиальная ДМТ-программа распознания L₂. Полиномиальная ДМТ-программа распознавания L₁ может быть получена композицией программ M и M₂. Ко входу применяем программу M для того, чтобы построить. Затем кf(x) применяется программа M₂, которая выясняет справедливость отношения . Так как по определению сводимости, то описанная ДМТ-программа распознает языкL₁. Полиномиальность этой программы следует из полиномиальности программ M и M₂. Точнее, если p и p₂ – полиномы, ограничивающие время работы программ M и M₂, то , и, следовательно, время работы только что определённой программы ограничено функцией, которая является полиномом от длиныx ч.т.д.

Если П₁ и П₂ – задачи распознавания, e₁ и e₂ – их схемы кодирования, то будем писать (относительно заданных схем кодирования), если существует полиномиальная сводимость языкак. На уровне задач полиномиальная сводимость задачи распознаванияП₁ к задаче распознания П₂ означает наличие функции , удовлетворяющей двум условиям:

1) f вычисляется полиномиальным алгоритмом.

2) Для всех ,.

ПРИМЕР.

Пусть G=(V, E) – граф с множеством вершин V и рёбер E. Простым циклом в графе G называется такая последовательность <v₁, v₂, … , v_k> различных вершин из V, что ,, и.

Гамильтоновым циклом в графе G называется простой цикл, содержащий все вершины G.

Задача распознавания ГАМИЛЬТОНОВ ЦИКЛ (ГЦ) формулируется так:

Задан граф G=(V, E).

Вопрос: Верно ли, что граф G содержит гамильтонов цикл?

Покажем, что ГЦ сводится к задаче КОММИВОЯЖЁР. Для этого требуется указать функцию f, переводящую каждую индивидуальную задачу I из задачи ГЦ в некоторую индивидуальную задачу из задачи КОММИВОЯЖЁР; f должна удовлетворять двум условиям, записанным ранее.

Пусть G=(V, E), |V|=m определяет фиксированную индивидуальную задачу из массовой задачи ГЦ. Соответствующая индивидуальная задача из массовой задачи КОММИВОЯЖЁР определяется следующим образом. Множество городов C совпадает с множеством вершин графа V. Для любых двух городов расстояние d(v_i, v_j)=1 если существует ребро в исходном графе (). Если ребро отсутствует, то соответствующее расстояние равно 2. В качестве границы B берётся величина m.

На неформальном уровне легко показать, что построенная функция преобразования f осуществляет сводимость и может быть вычислена за полиномиальное время. Для вычисления расстояний необходимо лишь выяснить принадлежность каждой пары вершин множествуE, т.е. не более указанного количества раз просмотреть это множество. Само вычисление значения m требует только однократного просмотра множества V, т.е. полиномиальные преобразования здесь очевидны. Для проверки справедливости второго требования необходимо показать, что граф G содержит гамильтонов цикл тогда и только тогда, когда в f(G) имеется проходящий через все города маршрут длины, не превосходящий B. Покажем это:

Пусть <v₁, v₂, …, v_m> – гамильтонов цикл в графе G, тогда <v₁, v₂, …, v_m> – маршрут длины m в задаче коммивояжёр f(G). Это так, поскольку для любой пары (v_i, v_i+1) и пары (v_m, v₁) имеются рёбра в исходном графе G, т.е. расстояния между городами равны 1.

Обратно:

Пусть <v_i1, v_i2, …, v_im> – маршрут в f(G), длина которого не превосходит B. Поскольку данный маршрут содержит ровно m пар городов, между которыми перемещается коммивояжёр, а любое расстояние в этой задаче не менее чем 1, то длина данного маршрута точно равна m. Следовательно, расстояние между каждой парой городов равно 1, это означает, что между каждой парой соответствующих вершин графа имеется ребро. Поэтому набор <v_i1,v_i2, …,v_im> определяет гамильтонов цикл в исходном графе G.

Итак, нами доказано, что ГЦ  КОММИВОЯЖЁР. В приведённом доказательстве имеются все элементы доказательства полиномиальной сводимости одной задачи к другой. Этот пример может служить моделью доказательства.

Отношение полиномиальной сводимости особенно удобно, поскольку является транзитивным. Это устанавливает следующая лемма.

Лемма 2. Если и , то .

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

Пусть – алфавиты языковL₁, L₂, L₃, функция реализует, а функцияреализует. Тогда функция, которая для всехопределяется соотношениемf(x) = f₂(f₁(x)), реализует полиномиальную сводимость . Действительно,f(x)L₃  x L₁, а полиномиальность вычисления функции f доказывается рассуждениями, аналогичными в приведённой лемме 1.

Языки L₁ и L₂ (соответственно задачи распознавания П₁ и П₂) полиномиально эквивалентны, если они сводятся друг к другу, т.е. и. Лемма 2 означает, что отношение полиномиальной сводимости является отношением эквивалентности. Кроме того, отношение сводимости определяет частичное упорядочивание возникающих классов эквивалентности языков (задач распознавания). На самом деле классP – «наименьший» относительно этого частичного порядка класс эквивалентности и с вычислительной точки зрения его можно рассматривать как класс «самых лёгких» языков (задач распознавания).