23. Сильная 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’, если:

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

2. Существуют такие полиномы от двух переменных 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). Это требование необходимо, поскольку мы будем рассматривать ограничения на индивидуальные задачи, которые формируются с помощью этих функций.