Лекция 9

Техника, используемая для доказательства NP-полноты подзадач, аналогична описанной ранее для изолированных задач. Но здесь имеется одно существенное отличие: когда мы пытаемся доказатьNP-полноту подзадачи, нам уже известно доказательствоNP-полноты некоторой обобщённой версии этой подзадачи. Это сразу нам подсказывает кандидата на известнуюNP-полную задачу. Кроме того, мы уже имеем доказательствоNP-полноты, которое можно попытаться модифицировать для получения доказательстваNP-полноты соответствующей подзадачи. Рассмотрим этот подход на примере.

РАСКРАШИВАЕМОСТЬ ГРАФА В ТРИ ЦВЕТА.

Условие:Задан графG=(V, E).

Вопрос: Верно ли, чтоGраскрашиваем в три цвета, т.е. существует ли такая функция f:V{1, 2, 3},такая, чтоf(u)f(v),если {u, v}E?

Сама по себе эта задача представляет собой частный случай задачи РАСКРАШИВАЕМОСТЬ ГРАФА В KЦВЕТОВ.k – число, входящее в условие задачи,f : V{1, 2, 3, …,k}.(задача РАСКРАШИВАЕМОСТЬ ГРАФА В ТРИ ЦВЕТА являетсяNP-полной)

Мы будем рассматривать задачу, вводя некоторые ограничения. Первое из них состоит из ограничения максимальной степени вершин. Большинство задач из теории графов может быть решено за полиномиальное время, если максимальная степень вершин достаточно мала. Например, если потребовать, чтобы все вершины графа имели степень не более двух, то задача ГЦ, ВЕРШИННОЕ ПОКРЫТИЕ и РАСКРАШИВАЕМОСТЬ ГРАФА В ТРИ ЦВЕТА тривиально решаемы за полиномиальное время. Таким образом, возникает вопрос, каково самое сильное ограничение на степени вершин при котором задача остаётся NP-полной. Задача КЛИКА – одна из задач, для которых никакое ограничение на степени вершин ни сохраняет свойстваNP-полноты.

Это свойство объясняется тем, что если степени вершин ограничены величиной D, то граф не может содержать клику состоящего более чем изDединиц вершин. Значит наибольшая клика может быть получена, если мы переберём все подмножества вершин, состоящие не более чем изD+1элементов. Количество таких подмножеств ограничено полиномом.

Замечание:

Хотя количество ограничено полиномом для любого D, однако, при больших Nи Dвремя решения уже не будет приемлемым. Для многих других задач имеютсяNP-полные подзадачи, с ограниченной степенью вершин. Некоторые представлены в следующей таблице:

	 P, при D 	NPC, при D 
ВП	2	3
ГЦ	2	3
РАСКРАШИВАЕМОСТЬ ГРАФА В 3 ЦВЕТА	3	4
МНОЖЕСТВО ВЕРШИН РАЗРЕЗАЮЩИХ КОНТУР	2	3

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

Граф называется планарным, если его можно отобразить на листе бумаги так, что никакие два ребра не пересекаются (единственно возможные точки пересечения – общие вершины). Например, при составлении географической карты и при конструировании платных схем возникают планарные графы. Задача КЛИКА снова даёт нам пример задачи, которая при наложении указанного условия упрощается. Это связано с тем, что никакой планарный граф не может содержать полного подграфа более чем на четырёх вершинах.

Рассмотрим в качестве примера задачу МАКСИМАЛЬНЫЙ РАЗРЕЗ.

Условие:Заданы графG=(V, E),весаw(e)Nкаждого ребра eE, и задано натуральное числоk.

Вопрос:Можно ли разбить множествоVна два непересекающихся подмножестваV₁ и V₂, таких, что сумма весов рёбер, имеющих в качестве концевых точек вершины из разных подмножеств, была не меньше, чемk.

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

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

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

Задачи с числовыми параметрами и сильная NP-полнота

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

В задаче РАЗБИЕНИЕ заданы множество A={a₁, a₂, … a_n} и натуральные веса элементовs(a₁), s(a₂), …, s(a_n). Положим. ЕслиBнечётно, то, очевидно, ответ в задаче будет “нет”. Если жеBчётно, то можно применить следующий подход. Рассмотрим функциюt(i,j),где 1in, 0jB/2. Значение этой функции определяет истинность утверждения «существует такое подмножество множества {a₁, a₂, … a_i}, что сумма размеров его элементов равнаj». Значение этой функции можно представить в виде таблицы.

Таблица заполняется построчно сверху вниз. Первая строка заполняется очевидным образом: значение истинности только в той ячейки, где j=0 илиj=s(a₁), все остальные ячейки заполнены значением “ложь”. Все следующие строки заполняются с использованием значений предыдущей строки, при этомt(i, j)=Tлибо приt(i-1, j)=T, либо приs(a_i)jиt(i-1, j- s(a_i))=T. Исходная задачаразбиениедаёт ответ “да” в том случае, когда значение таблицыt(n,B/2)=T. Рассмотрим заполнение таблицы на следующем примере:

A={a₁,…, a₅} s(a₁)=1, s(a₂)=9, s(a₃)=5, s(a₄)=3, s(a₅)=8; B=26

i/j

0

1

2

3

4

5

6

7

8

9

10 1101

11

12

13

1

T

T

2

T

T

T

T

3

T

T

T

T

T

T

4

T

T

T

T

T

T

T

T

T

T

T

5

T

T

T

T

T

T

T

T

T

T

T

T

Как видно из решения, алгоритм является полиномиальным алгоритмом со сложностью порядка количества элементов таблицы, т.е. nB. Может показаться, что этот алгоритм даёт полиномиальное решение задачиразбиение. Однако это не так, поскольку мы предполагаем, что используется разумная схема кодирования. Для таких схем кодирования любое целое числоs(a_i) представляется на входе длины не более чемlog₂s(a_i). Это означает, что длина входа будет порядкаnlog₂B. ВеличинаnBне может быть ограничена полиномом от величиныnlog₂B, т.е. задача не является полиноминально разрешимой.

Наличие подобного алгоритма показывает, что NP-полнота задачиразбиениев значительной степени зависит от того обстоятельства, что на входе могут присутствовать чрезвычайно большие числа. Если на величину входных чисел было бы положено ограничение, например в виде полинома от размера задачи, то приведённый алгоритм для этой ограниченной задачи был бы полиномиальным. Алгоритмы с таким свойством называются «алгоритмами с псевдополиномиальным временем работы». На практике большое количество задач имеют входные данные, удовлетворяющие предложенному ограничению. Однако и в ситуациях, когда такое ограничение не выполняется, псевдополиномиальные алгоритмы полезны. Они будут работать экспоненциально долго только для тех индивидуальных задач, которые имеют экспоненциально большие числа. Однако может оказаться, что в интересующих нас приложениях подобные индивидуальные задачи встречаются редко, т.е. псевдополиномиальный алгоритм будет служить почти всегда так же хорошо, как и полиномиальный. Однако не все задачи с числовыми параметрами имеют алгоритмы, подобные рассмотренному. С помощью теорииNP-полноты можно показать, что для некоторых задач не может существовать даже псевдополиномиального алгоритма. Введём некоторые дополнительные определения. В этих определениях учитывают подзадачи, которые получаются при наложении ограничений на величины чисел, входящих в индивидуальную задачу. Эти ограничения формулируются с помощью двух не зависящих от кодирования функций.

Length : D_ПN

Max : D_ПN.

Функция Lengthсопоставляет любой индивидуальной задаче число, соответствующее длине описания этой задачи. ФункцияMaxсопоставляет индивидуальной задаче число, соответствующее величине максимального числа. Результаты, которые в дальнейшем будут получены, справедливы для достаточно широкого класса полиномиально эквивалентных функцийLengthиMax. Будем говорить, что функцииLengthиLength’ полиномиально эквивалентны, если существуют полиномыpиp’такие, что для любой индивидуальной задачиID_ПLength(I) p’(Length’(I)) иLength’(I)p (Length(I)).

Будем говорить, что пара функций MaxиLengthполиномиально эквивалентныMax’иLenght’, если:

Функции LengthиLength’ полиномиально эквивалентны.

Существуют такие полиномы от двух переменных qиq’, что для всехID_Пвыполняются неравенства:

Max(I)  q’ (Max’(I), Length’ (I))

Max’(I)  q (Max (I), Length (I)).

В качестве примера рассмотрим функции MaxиLength, которые задаются для задачираЗбиение. В этой задаче любая индивидуальная задача задаётся конечным множествомAи размерами всех элементовs(a_i).

Функцию Maxможно выбрать следующим образом:

; ;

В качестве функции Lengthможно выбрать любую из следующих функций:

Любая из девяти пар, заданных функциями MaxиLength, полиномиально эквивалентна любой другой паре. Понятие полиномиальной эквивалентности пар функцийMaxиLengthпозволяет при построении доказательств не указывать конкретно эти функции, а ссылаться только на разумность кодировки. Предлагаемые функции имеют целочисленные значения, а числовые параметры могут представлять собой более сложные образования. Такие числа будем рассматривать как совокупность нескольких целых чисел. Примем следующее соглашение: в качестве значенияMax(I) будем выбирать либо величину наибольшего числа входящего вI, либо 0, если вIне входят числа. От функцииLengthиMaxпотребуем выполнения ещё одного условия. При любой фиксированной, разумной схеме кодирования должны существовать две ДМТ программы с полиномиальным временем работы. Они, принимая на входе условие произвольной индивидуальной задачи, выдают двоичные записи величинMax(I),Length(I). Это требование необходимо, поскольку мы будем рассматривать ограничения на индивидуальные задачи, которые формируются с помощью этих функций.

Следующие определения предполагают, что с массовой задачей Псвязаны функцииMaxиLengthобладающие ранее указанными свойствами. Алгоритм решения задачиП, будет называться псевдополиномиальным (по времени) алгоритмом, если его временная функция ограничена сверху полиномом от (Length(I),Max(I)). По определению, любой полиномиальный алгоритм является также и псевдополиномиальным, поскольку ограничен сверху полиномом от первого аргумента (Length(I)).NP-полнота задачи не обязательно исключает возможность её решения псевдополиномиальным алгоритмом. Многие из рассмотренных нами задач обладают тем свойством, что величинаMax(I) ограничена полиномом отLength(I), поэтому для таких задач нет различия между полиномиальным и псевдополиномиальным алгоритмами. Например, в задачекликаединственной числовой параметрIограничен количеством вершин графа. Задачавыполнимостьне содержит чисел, за исключением индексов, литералов, дизъюнкций, этими числами можно пренебречь, поскольку они играют роль имён. Принятое нами соглашение о разумной схеме кодирования гарантирует, что имена будут ограничены полиномомLength(I).

Выделим класс задач, которые будут рассматриваться в данном разделе. Будем называть задачу Пзадачей с числовыми параметрами, если не существует такого полиномаp, что для любой задачиID_ПMax(I)p(Length(I)). Среди шести основныхNP-полных задач единственной задачей с числовыми параметрами является задачаразбиение.

Замечание 1.

Если NP-полная задача П не является задачей с числовыми параметрами, то П не может быть решена псевдополиномиальным алгоритмом (если справедливо, что P  NP).

Для произвольной задачи Пи полиномаpс целыми коэффициентами обозначим черезП_pподзадачу, получаемую изП рассмотрением только тех индивидуальных задачI, для которых выполняетсяMax(I)p(Length(I)). ЗадачаП_pуже не является задачей с числовыми параметрами. Если задача Празрешима псевдополиномиальным алгоритмом, то задачаП_pразрешима полиномиальным алгоритмом. ЗадачуПназовёмNP-полнойв сильном смысле, еслиПNPи существует такой полиномpс целыми коэффициентами, что задачаП_p являетсяNP-полной.

В частности, если NP-полная задача не является задачей с числовыми параметрами, то онаNP-полна в сильном смысле.

Замечание 2.

Если задача П NP-полна в сильном смысле, то она не может быть решена псевдополиномиальным алгоритмом (при PNP).

Благодаря этому замечанию мы получаем средства для применения теории NP-полноты к вопросам существования псевдополиномиальных алгоритмов.