Лекция 11

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

Условие:Задано конечное множество задачTдля каждойtT, r(t)0– время готовности, кроме того, дан директивный срокd(t)Nи длительностьl(t)N.

Вопрос:Существует ли дляTдопустимое расписание, т.е. такая функция : TN₊₀, что для всех tT

(t)  r(t);

(t)+l(t)  d(t);

 t’ T\{t} или (t’)+l(t’)  (t), или (t’)  (t)+l(t).

Построим псевдополиномиальное сведение задачи 3-разбиениек задачеупорядочивание внутри интервалОВ:

A={a₁, a₂, … a_3m}, BN. Веса S(a₁), S(a₂), … S(a_3m)определяют задачи из3-разбиение. Соответствие индивидуальной задачи изупорядочивание внутри интерваловстроится следующим образом:

T=A{t_i:1i<m}.

, гдеl(t)– время обработки детали;

, гдеr(t)– время готовности;

, гдеd(t)– директивный срок работы.

Описанная сводимость может быть выполнена за полиномиальное время только по отношению к длине записей сходной информации. Длина исходных задач, получаемых при таком сведении полиномиально эквивалентна длине исходных задач, т.е. условие 2 и 3 определения выполняются. При сведении наибольшее число построенной индивидуальной задачи равно mB+m-1, следовательно, выполняется условие 4, остаётся показать, что выполнено условие 1.

В любой последовательности заданий, удовлетворяющей условиям построенной задачи, задание t_iдолжно выполнятся в промежутке времени отiB+i-1, до iB+1, что можно изобразить следующим рисунком:

Таким образом, мы имеем nинтервалов, каждый — длиныB. Поскольку совокупная длина интервалов равна последнему сроку выполнения самого последнего задания, то все пустые блоки должны быть не полностью заполнены выполняющимися заданиями. Таким образом, эти блоки играют в задачеупорядочивание внутри интерваловту же роль, что и множествоS₁, S₂, …, S_nв задаче3-разбиение, значит условие а) также выполняется, и мы имеем псевдополиномиальную сводимость задачи, поэтому задачаупорядочивание внутри интерваловNP-полна в сильном смысле ч.т.д.

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

Временная сложность как функция натуральных параметров

До сих пор мы рассматривали подзадачи из-за того, что на практике истиной целью является решение конкретной задачи, а не самой общей массовой задачи. Зная очертания пограничной области между NP-полными и полиномиально разрешимыми подзадачами, мы сможем решать конкретную подзадачу, двигаясь в наиболее перспективном направлении. С другой стороны, результаты, полученные относительно подзадач, могут быть использованы в качестве ориентира при поиске алгоритма общей задачи. Если общая задача оказываетсяNP-полной, то при справедливостиPNPдля её решения могут существовать только экспоненциальные алгоритмы. Однако различные алгоритмы решения могут оказаться в различной степени “экспоненциальными”. При этом одни из них могут оказаться для нас предпочтительнее других. Это связано с тем, что в практических задачах мы имеем дело с конкретными параметрами, а не с искусственно созданной длиной входа. В задачирасписание для мультипроцессорной системынабор естественных параметров включает следствия величины:

число заданий n;

число процессоров m;

длительность Lсамого продолжительного задания.

Результат о NP-полноте этой задачи утверждает, что она не может быть решена за время ограниченная полиномом от трёх переменныхn, m, log L. Однако, можно задаться вопросом: существует ли алгоритм, временная сложность которого ограничена полиномом отmⁿ иlogLили отn^m иlogL, или отn, m, L, или от(nL)^m. Полученные результаты о сложности подзадач проливают некоторый свет на эти вопросы. Исходный результат оNP-полноте рассматриваемой задачи показывает в действительности, что подзадача, в которойmограниченно числом 2, являетсяNP-полной, поэтому для решения задачи не может существовать алгоритма, временная сложность которого ограничена полиномом отn^m иlogL, для такой подзадачи этот алгоритм был бы полиномиален. В тоже время, полученные результаты не исключают возможности существования алгоритма, временная сложность которого ограничивалась бы полиномомmⁿ log L(в действительности алгоритмы полного перебора с такой временной сложностью могут быть построены). Поскольку задача, которую мы рассматриваем, является, кроме того,NP-полной в сильном смысле, это исключает существование алгоритмов полиномиальных поn, m, L. Однако этот результат оставляет открытым вопрос о существовании алгоритма, полиномиального по(nL)^m(такой алгоритм давал бы псевдополиномиальный алгоритм при каждом фиксированномm).

Задача расписание для мультипроцессорной системы.

Условие:Задано множествоAзаданий; длительностиl(a)N для всехaA, числоm процессовmN, директивное числоDN.

Вопрос: Существует ли разбиениеAнаmнепересекающих подмножествA=A₁A₂…A_m, такое, что.

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

Таким образом, рассматривая подзадачи, возникающие из исходной задачи при ограничении одного или нескольких из её естественных параметров, мы получаем полезную информацию о возможных типах алгоритмов решения общей задачи. Однако, чтобы обеспечить выразимость функции Length(I)в виде полинома от параметров, выбранных нами в качестве достаточных представителей размера индивидуальной задачи, нужно принять особые меры предосторожности (необходимо, чтобы для исходной задачи класс распространённых полиномиальных алгоритмов совпадал с классом алгоритмов, полиномиальных относительно выбранных параметров, в остальном можно выбирать любые параметры, которые представляются естественными и адекватно отражающими смысл задачи). Из общего результата обNP-полноте будет вытекать, что задачу нельзя решить за время, ограниченное полиномом от всех выбранных параметров, но информация, получаемая при ограничении этих параметров, может иметь большое значение в связи с существованием общих алгоритмов других типов. Методы, аналогичные методам отыскания сильнойNP-полноты, можно применять и к задачам, не имеющим числовые параметры (в нашем определении). Дело в том, что в любой задачи неявно присутствуют числовые параметры, такие как мощности множества, значение границ и т.д. Например,NP-полнота задачи3-выполнимость не допускает алгоритма для задачивыполнимость, временная сложность которого ограниченна полиномом от(mn)^M:

m– число дизъюнкций,

n– число литералов,

M– максимальное число литералов в одной дизъюнкции.

С другой стороны, для задачи кликасуществует алгоритм с временной оценкойn^D, гдеn– число вершин графа,D– максимальная степень вершин. Таким образом, теорияNP-полных задач может служить ориентиром не только при поиске полиномиальных алгоритмов, но и экспоненциальных.