двух полиномиальных алгоритмов (выход первого алгоритма подается на вход второго) также работает полиномиальное время. Объясняется это тем, что сумма, произведение и композиция многочленов снова есть многочлен. Абстрактные задачи

Мы принимаем следующую абстрактную модель вычислительной задачи. Будем называть абстрактной задачей (abstract problem) произвольное бинарное отношение Q между элементами двух множеств - множества условий (instances) I и множества решений (solutions) S. Например в задаче SHORTEST-PATH (поиск кратчайшего пути между двумя заданными вершинами некоторого неориентированного графа G = (V, Е)) условием (элементом Е) является тройка, состоящая из графа и двух вершин, а решением (элементов S) - последовательность вершин, составляющих требуемый путь в графе. При этом один элемент множества I может находиться в отношении Q с несколькими элементами множества S (если кратчайших путей между данными вершинами несколько)

В теории NP-полноты рассматриваются только задачи разрешения (decision problems) - задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Формально задачу разрешения можно рассматривать как функцию, отображающую множество условий I в множество {0,1} (1 = «да», 0 = «нет»). Многие задачи можно там или иным способом преобразовать к такому виду. Например, с задачей поиска кратчайшего пути в графе связана задача разрешения PATH: «по заданному графу G = (V,E), паре вершин и, v G V и натуральному числу к определить, существует ли в С путь между вершинами и и v, длина которого не превосходит к». Пусть четверка г = (G,u,v,k) является условием задачи PATH. Тогда РАТН(г) = 1, если длина кратчайшего пути между вершинами и и v не превосходит к, и РАТН(г) = 0 в противном случае.

Часто встречаются задачи оптимизации (optimization problems), в которых требуется минимизировать или максимизировать значение некоторой величины. Прежде чем ставить вопрос о NP-полноте таких задач, их следует преобразовать в задачу разрешения. Обычно в качестве такой задачи разрешения рассматривают задачу проверки, является ли некоторое число верхней (или нижней) границей для оптимизируемой величины. Так, например, мы перешли от задачи оптимизации SHORTEST-PATH к задаче разрешения PATH, добавив в условие задачи границу длины пути к.

Если после этого получается NP-полная задача, то тем самым установлена трудность исходной задачи. В самом деле, если для оптимизационной задачи имеется быстрый алгоритм, то и полученную из неё задачу разрешения можно решить быстро (надо просто сравнить ответ этого алгоритма с заданной границей). Таким образом, теорию NP-полноты можно использовать и для исследо-

вания задач оптимизации. Представление данных

Прежде чем подавать на вход алгоритма исходные данные (то есть элемент множества /), надо договориться о том, как они представляются в «понятном для компьютера виде»; мы будем считать, что исходные данные закодированы последовательностью битов. Формально говоря, представлением элементов некоторого множества S называется отображение е из S во множество битовых строк. (Разумеется, вместо битовых строк можно было бы рассматривать последовательности символов любого другого конечного алфавита, имеющего не менее двух символов.) Например, натуральные числа 0,1,2,3,... обычно представляют битовыми строками 0,1,10,11,100,... (при этом, например, е(17) = 10001). В компьютерах для представления букв и других символов используют код ASCII (реже - EBCDIC). Так, е(А) = 1000001 в коде ASCII.

Фиксировав представление данных, мы превращаем абстрактную задачу в строковую, для который входным данным является битовая строка, представляющая исходное данное абстрактной задачи. Будем говорить, что алгоритм решает (solves) строковую задачу за время 0(Т(п)), если на входном данном (битовой строке) г длины п алгоритм работает время 0(Т(п)). Строковая задача называется полиномиальной (polynomial-time solvable), существует константа к и алгоритм, решающий эту задачу за время 0(пк).

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

Желая определить понятие полиномиальной абстрактной задачи, мы сталкиваемся с тем, что возможны различные представления данных. Для каждого представления е множества / входов абстрактной задачи Q мы получаем свою строковую задачу, которую мы в дальнейшем обозначаем e(Q). Вообще говоря, при одном представлении может получиться полиномиальная строковая задача, а при другом - нет. (Тут есть ещё одна - чисто техническая - деталь: некоторые битовые строки могут не представлять никаких исходных данных; что требуется в этом случае от алгоритма, решающего строковую задачу? Будем считать, что он должен давать в этом случае ответ 0, то есть что свойство e(Q) ложно для таких входов.)

Вернёмся к вопросу о том, как зависит полиномиальность задачи от выбранного представления. Пусть, например, входом задачи является натуральное число к, и время работы алгоритма есть Q(k). Если число к представить в системе счисления с основанием 1 (unary representation), то есть в виде последовательности к единиц, то время работы алгоритма на входе длины п будет равно О(п), и алгоритм будет полиномиальным. При более естественном двоичном представлении числа к время работы на входе длины п (то

есть на га-битовом числе) будет равно в(2й), и алгоритм не будет полиномиальным.

Однако на практике (если исключить такие «дорогие» способы представления, как система счисления с основанием 1) естественные способы представления оказываются обычно эквивалентными, поскольку они могут быть быстро (полиномиально) преобразованы друг в друга. Например, двоичную запись числа можно преобразовать в троичную и обратно за полиномиальное время.

Будем говорить, что функция / : {0,1}* -> {0,1}* вычислима за полиномиальное время (is polynomial-time computable), если существует полиномиальный алгоритм А, который для любого ж G {0,1)* выдает результат /(ж).

Рассмотрим теперь множество I условий произвольной абстрактной задачи разрешения. Два представления е\ и е2 этого множества называются полиномиально связанными (polynomially related), если существуют две вычислимые за полиномиальное время функции ода /12 и /21, для которых /12(1 (i)) = е2(г) и /2i(e2(0) = ei(0 для всякого i €. I. Это значит, что е\-представление входа может быть за полиномиальное время получено из е2-представления и наоборот. В этом случае не имеет значения, какое из двух полиномиально связанных представлений выбрать, как показывает следующая лемма.

Лемма 36.1

Пусть Q - абстрактная задача разрешения с множеством условий I, а е\ и в2 - полиномиально связанные представления для элементов множества I. Предположим, что множество всех строк, которые являются ei-представлениями элементов Q, разрешимо за полиномиальное время, и что аналогичное свойство выполнено для представления е2. Тогда свойства e\(Q) G Р и e2(Q) G Р равносильны.

Доказательство. Утверждение симметрично, так что достаточно доказать его в одну сторону. Предположим, что задача e\(Q) разрешима за время 0(пк) для некоторого фиксированного числа к. По предположению для всякого условия i £ I представление ei (г) может быть получено из представления в2(г) за время 0(пс) (где с - некоторая константа, га = е2 (*) ) - Для решения задачи e2(Q), получив на вход в2(г), мы сперва вычислим ei (г), а затем применим алгоритм, разрешающий ei(Q), к строке ei (г). Сколько времени займёт наше вычисление? Преобразование в2(г) в ei (г) требует полиномиального времени. Следовательно, ei(i) = 0(пс), поскольку длина выхода алгоритма не превосходит времени его работы. Решение задачи с условием ei (г) занимает 0(\ei(i)\k) = 0(пск) времени. Итак, время вычисления оказалось полиномиальным. (Мы пропустили важный момент: получив на входе некоторую строку, мы должны сначала проверить, что она является е2-представлением некоторого входа; по предположению это можно сделать за поли-