21. Методы доказательства np-полноты. Метод построения компонент. Некоторые методы доказательства np-полноты.

Имеется несколько общих приёмов из большого количества подходов доказательства NP-полноты, которые широко используются. Эти приёмы:

а) Сужение задачи.

б) Локальная замена.

в) Построение компонент.

Метод построения компонент.

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

ПРИМЕР.

Докажем полноту NP-полной задачи УПОРЯДОЧЕНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ.

Условие: Задано множество T заданий, каждое из которых имеет длительность 1, для каждого задания задан директивный срок d(t)N₊₀; частичное упорядочивание (<·) на множестве T и целое неотрицательное k|T|.

Вопрос: Существует ли расписание  : T{0,1,2, … , |T|-1}, такое, что

1. tt’(t)(t’).

2. (t)<(t’) если t <· t’.

3. |{tT : (t)+1d(t)}|  k.

Докажем NP-полноту задачи.

П усть граф G=(V, E) и положительное целое число J (J|V|) образуют индивидуальную задачу из массовой задачи КЛИКА. Соответствующая индивидуальная задача из задачи УПОРЯДОЧЕНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ имеет множество заданий T=VE, величина k=|E|-J(J-1)/2. Частичное упорядочивание заданий определяется следующим образом:

t <· t’  tV, t’E и вершина t инцидентна ребру t’;

Таким образом, компонента, соответствующая каждой вершине, состоит из единственного задания с директивным сроком |V|+|E|, а компонента, соответствующая каждому ребру, состоит из единственного задания с директивным сроком J(J+1)/2. Благодаря наличию частичного порядка на множестве T в искомом расписании задание, соответствующее ребру, будет следовать за заданиями, соответствующими его вершинам. Поэтому задания, для которых имеется опасность запаздывания, обязательно соответствуют рёбрам. Искомое расписание удобно представить себе схематически следующим рисунком:

Первые две части из четырёх частей расписания можно рассматривать как компоненту выбора клики. До этого срока может быть выполнено не более J(J+1)/2 заданий. Для того чтобы число запоздавших заданий не превосходило заданной вершины k, в начале должны стоять, по крайней мере, J(J-1)/2 заданий, соответствующих рёбрам. Однако если задание, соответствующее ребру, выполняется ранее своего директивного срока, то и задания, соответствующие его концевым вершинам должны быть закончены раньше этого срока. Минимально возможное количество вершин, которые могут быть инцидентны J(J-1)/2 различным рёбрам, равно J (причём такая ситуация возможна только тогда, когда эти рёбра образуют полный граф на указанных J вершинах). Отсюда следует, что среди заданий, выполняющихся ранее директивного срока, должно иметься, по крайней мере, J заданий, соответствующих вершинам. Однако до директивного срока заданий, соответствующих рёбрам, может быть выполнено не более J(J+1)/2 - J(J-1)/2 = J заданий, отвечающих вершинам. Следовательно, в любом таком расписании до директивного срока заданий, соответствующих рёбрам, должно закончится ровно J заданий, соответствующих вершинам, и ровно J(J-1)/2 – рёбрам, что соответствует клике исходного графа G. Обратно, если клика существует, то расписание можно построить способом, указанном на рисунке.