Взаимоотношение между классами 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 имеет структуру:

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

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

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, что,-1, и.

Гамильтоновым цикломв графе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– «наименьший» относительно этого частичного порядка класс эквивалентности, и с вычислительной точки зрения его можно рассматривать как класс «самых лёгких» языков (задач распознавания). КлассNP-полных языков (задач распознания) даёт нам другой класс эквивалентности. В этом классе содержатся самые трудные языки (задачи распознавания) из классаNP.

ЯзыкLназываетсяNP-полным, еслиLNPи любой другой языкL’NPсводится к L. Исходя из свойств полиномиальной сводимости, можно сказать, чтоNP-полные задачи являются самыми трудными задачами классаNP, поскольку полиномиальное решение любой задачи означает полиномиальное решение всех задач классаNP. С другой стороны, если хотя бы одна задача классаNP

труднорешаема, то и все NP-полные задачи труднорешаемы. Предположим, чтоPNP, тогда можно дать следующую уточнённую характеристику классаNP.

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

Лемма 3:

Если L₁, L₂NP, L₁NPC и , тоL₂NPC.

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

Поскольку L₁NPC, то L’NP L’  L₁, тогда согласно лемме 2 имеем, что любая задача изNPсводится к L₂, т.е.L₂NPC.

На уровне задач распознавания эта лемма указывает простой путь доказательства NP-полноты, если нам известна хотя бы однаNP-полная задача.

Для доказательства NP-полноты задачиПнеобходимо показать:

1) П NP.

2) Какая либо известная NP-полная задача полиномиально сводится к задаче П.

Наличие класса NP-полных задач доказывает теорема Кука.