SEP Apr May 29 2008 2009 2010 14 captures 29 Sep 04 - 29 Apr 09

Close Help

Литература:

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

2. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.

§ 1. Понятие о сложности решения задач

Основные определения: индивидуальная и массовая задачи, кодировка, алгоритм решения массовой задачи, временн'ая сложность алгоритма. Классы P и NP (формальные определения, примеры).

1. На вопрос, для чего надо иметь представление о сложности решаемых задач, наиболее наглядный ответ дан во введении к книге [1]. В этой книге также приводится более 500 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых в настоящее время нет оснований надеяться построить эффективные алгоритмы их решения. Что это значит формально, будет рассказано в данном разделе (§§ 1-4), а соответствующие практические выводы каждый человек, так или иначе связанный с разработкой алгоритмов и программ, делает для себя сам. Кроме того, теория сложности - новая, модная, интенсивно развивающаяся область математики и кибернетики, ее терминология широко распространена в современной научной литературе и требует определенного с ней знакомства.

Появление вычислительной техники привело к тому, что все реже приходится решать отдельную конкретную задачу, а все больше писать программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому имеет смысл говорить о сложности не для одной индивидуальной задачи I, а для массовой задачи, или проблемы П, соответствующей множеству индивидуальных задач.

Формально массовая задача П определяется

1⁰ общим списком всех параметров задачи (свободных параметров, значения которых не заданы),

2⁰ формулировкой свойств, которым должен удовлетворять ответ (решение задачи).

Индивидуальная задача I О П получается из П, если всем параметрам присвоить конкретные значения.

Для примера рассмотрим задачу коммивояжера: найти минимальный маршрут обхода группы объектов (условно говоря, городов) с возвратом в начальную точку. Для П коммивояжера введем

1⁰ входные параметры:  число городов m или множество городов
C = {c₁, ј, c_m} и набор расстояний между городами

{d(ci,cj) > 0:   ci, cj О C,  i № j};

2⁰ требования к решению:  [c_p(1), ј, c_p(m)]   реализует   

min p  й л m-1 е i = 1  d(cp(i),cp(i+1)) + d(cp(m),cp(1)) щ ы ,

где минимум берется по всем возможным перестановкам p на множестве индексов городов. Конкретизируем параметры 1⁰, чтобы получить индивидуальную задачу I коммивояжера: m = 4, d(c₁,c₂) = 10, d(c₁,c₃) = 5, d(c₁,c₄) = 9, d(c₂,c₄) = 9, d(c₃,c₄) = 3, d(c₃,c₂) = 6, d(c_i,c_j) = d(c_j,c_i).  Тогда в задаче I оптимальным оказывается маршрут [c₁,c₂,c₄,c₃],  реализующий путь минимальной длины 27.

Кроме первичных понятий массовой и индивидуальной задачи (П и I) мы будем использовать термин алгоритм и обозначение А для пошаговой процедуры (решения задачи), в частности машины Тьюринга или программы для ЭВМ. Будем говорить, что алгоритм А решает массовую задачу П, если для любой индивидуальной задачи I О П алгоритм А применим к I (т.е. останавливается за конечное число шагов) и "I О П алгоритм А дает решение задачи I. Например, для П коммивояжера существует алгоритм, который решает ее на основе полного перебора всех маршрутов (перестановок p).

Большинство дискретных и комбинаторных задач допускает решение с помощью некоторого процесса перебора вариантов, однако число возможных вариантов растет экспоненциально в зависимости от размеров задачи (так, в задаче коммивояжера m! маршрутов). Поэтому переборные алгоритмы решения массовых задач считаются неэффективными (могут решать лишь небольшие индивидуальные задачи). В отличие от них эффективными называются полиномиальные алгоритмы решения массовой задачи, т.е. такие, которые решают произвольную I О П за время, ограниченное полиномом от ``размера" I. Несмотря на определенную условность этого разделения с точки зрения практического счета, оно объясняется прежде всего тем, что центральным для дискретной оптимизации является вопрос, можно ли построить алгоритм решения массовой задачи (т.е. любой индивидуальной), не перебирающий всех или почти всех вариантов ее решения. Если для массовой задачи П существует полиномиальный алгоритм, ее решающий, значит, ее можно решить не путем перебора - эффективно. Указанные задачи П называются полиномиальными. Перейдем к их формальному определению.

2. Формализация проводится для задач распознавания свойств. Это - массовые задачи, предполагающие ответ ``да" или ``нет" в качестве решения. Таким образом, в п.2⁰ определения П распознавания свойств стоит некоторый альтернативный вопрос и решением каждой индивидуальной задачи I О П является правильное распознавание, принадлежит ли она к задачам с ответом ``да". Последнее подмножество множества индивидуальных задач будем обозначать Y. Теперь введем обозначение D для множества всех возможных значений параметров, заданных в п.1<sup>0</sup> определения П. Очевидно, что набор [D(П),Y(П)] полностью характеризует соответствующую массовую задачу П распознавания свойств. Несмотря на специфичность постановки, класс задач распознавания свойств является достаточно широким: по крайней мере, для любой задачи дискретной оптимизации можно указать аналогичную П распознавания свойств. В частности, для П коммивояжера, если ввести в п.1<sup>0</sup> еще один параметр B - длину маршрута, то вопрос в п.2<sup>0</sup> ``существует ли маршрут длины, не превышающей B?" дает ее переформулировку как задачи распознавания свойств. Полученная П коммивояжера имеет в литературе обозначение КМ (или ЗК [2]), для нее

D(КМ) = {C,  {d(ci,cj) О Z+| ci, cj О C,  i < j},  B О Z+}.

Здесь и далее Z₊ - множество натуральных чисел, Z - целых.

Для формализации ``размера" индивидуальной задачи свяжем с каждой проблемой П определенную схему кодирования (кодировку). Введем конечное множество - алфавит S = {S_i}, например S = {0, 1}, а также множество S^* слов над алфавитом S - произвольных конечных последовательностей, составленных из символов алфавита, возможно повторяющихся, S = S_i1 S_i2јS_in,   S_ij О S  "i_j ; например, пустое множество Ж или 011000. Число n называется длиной слова S и обозначается знаком модуля, n = |S|. Кодировкой задачи П назовем такое отображение e: П® S^*, ставящее в соответствие любой индивидуальной задаче I О П ее код  e(I) = S О S^* (слово из алфавита S^*), что

1^* возможно однозначное декодирование:  "I₁ № I₂   e(I₁) № e(I₂);

2^* e, e^-1 полиномиально вычислимы: существует алгоритм, реализующий e, e^-1, и полином p(·), для которого "I О П время определения e(I) и e^-1(e(I)) не превосходит p(|e(I)|);

3^* кодировка неизбыточна: для любой другой кодировки eў, удовлетворяющей условиям 1^*,2^*, найдется полином pў(·) такой, что "I О П  |e(I)| < pў(|eў(I)|). Например, для записи целых чисел неизбыточной является любая k-ичная система счисления с k > 1, кодировка чисел тем же количеством палочек (случай k = 1) избыточна.

УПРАЖНЕНИЕ 1. Предложить неизбыточную кодировку и оценить по порядку длину входа задачи коммивояжера, сравнить полученную оценку с указанной в [1] на с. 35:

             m + йlog₂ B щ+ max{ йlog₂ d(c_i,c_j)щ| c_i,c_j О C }.
Здесь и далее знаком й·щ обозначается ближайшее целое сверху к числу в скобках, а л·ы - целая часть числа.

Начиная с этого момента, в §§ 1-3 мы будем, как правило, рассматривать П распознавания свойств, оговаривая другие случаи особо.

После того как для массовой задачи П введена кодировка, с любой индивидуальной задачей I О П будет связано некоторое слово S в алфавите S этой кодировки. Слова, которые соответствуют индивидуальным задачам распознавания свойств, имеющим ответ ``да", условимся считать ``правильными" и множество правильных слов в S^* назовем языком. Формально, язык L(П,e) := e(Y(П)) :=

:= {S О S* | S - алфавит e,  S = e(I),  I О Y(П)}.

С алгоритмом А решения задачи П распознавания свойств будем ассоциировать машину Тьюринга (программу для детерминированной машины Тьюринга) с входным алфавитом S и конечными состояниями q_Y (``да") и q<sub>N</sub> (``нет") и аналогично назовем языком алгоритма А множество слов, принимаемых А (с которыми на входе А останавливается в состоянии q_Y - ``да"),

L(А) := {S О S* | S - алфавит А, и А(S) = qY}.

Определение 1. Алгоритм А решает массовую задачу П с кодировкой e, если L(А) = L(П,e) и "S О S^*  А останавливается. Обозначим t_А(S) время работы над словом S О S^*  (число шагов) алгоритма А до остановки. Временн'ой сложностью алгоритма А решения массовой задачи П назовем функцию T_А(·), определяемую как

TА(n) = max S О S*: |S| < n   tА(S)   "n О Z+.

Таким образом, при оценке временн'ой сложности алгоритмов мы рассчитываем на ``худшую" из возможных индивидуальных задач (данного размера), поскольку заранее не известно, с какой конкретной задачей придется работать.

УПРАЖНЕНИЕ 2. Дать алгоритм распознавания простоты числа, оценить временн'ую сложность алгоритма.

Определение 2. Класс полиномиально разрешимых задач

P := {L(П,e)| $А, решающий П с кодировкой e,  $p(·) - полином:  T_А(n) < p(n)   "n О Z₊}.

Если для задачи П существует такая кодировка e, что L(П,e) О P, то будем называть задaчу П полиномиально разрешимой или просто полиномиальной и пользоваться обозначением П О P, отождествляя массовую задачу и язык. (С учетом условия неизбыточности кода указанная процедура корректна, ибо для полиномиальной П получаем L(П,e) О P   "e.)

Примером полиномиальной задачи является распознавание четности целого числа. (С еще одной полиномиальной задачей мы встретимся в разд.2.) Для задачи распознавания простоты числа (ПЧ) вопрос о ее полиномиальности пока открыт. Для ряда других задач удается доказать их неполиномиальность. Так, известны

1) алгоритмически неразрешимые задачи, когда не существует алгоритма, решающего любую индивидуальную задачу, т.е.  "А
$I О П:  А не применим к I, в частности,  t_A(e(I)) = Ґ ; например, 10-я проблема Гильберта: по данному многочлену g с целыми коэффициентами выяснить, имеет ли уравнение g = 0 целочисленное решение (неразрешимость доказал Ю. М. Матиясевич в 1970 г.);

2) задачи (не являющиеся задачами распознавания свойств), для которых длина записи решения превосходит любой наперед заданный полином от длины входа, например в задаче коммивояжера, если требуется найти все маршруты (их экспоненциальное число);

3) в остальных случаях формально имеем "А, решающего П с кодировкой e,   "p(·)   $I О П:  t_А(e(I)) > p(|e(I) |).  Здесь и далее p(·), возможно с индексами, служит для обозначения полиномов.

В настоящее время для любой массовой задачи П, для которой доказано последнее условие, получен и более сильный результат: отсутствие полиномиального алгоритма, использующего произвольное (пусть бесконечное) число параллельных процессоров. Вопрос, существуют ли неполиномиальные задачи П распознавания свойств, которые оказываются полиномиально разрешимыми при возможности распараллеливания вычислений, является основной методологической проблемой теории сложности (обусловившей ее формирование как самостоятельной научной дисциплины). Ответ, по-видимому, должен быть положительным, и уже указан большой класс массовых задач в качестве кандидатов (см. класс NPC в § 2), но доказать или опровергнуть эту гипотезу в данный момент представляется нереальным. Для ее формализации вводится объемлющий P класс недетерминированно полиномиальных задач - NP.

3. Определим недетерминированную машину Тьюринга (НДМТ) [^(A)] как набор обычных - детерминированных - машин Тьюринга (ДМТ) A(S) с алфавитом S, где S пробегает все множество слов из S^* :

[^(A)] := {A(S)}S О S* .

НДМТ [^А] останавливается, когда останавливается первая из ДМТ А(S), принимающая входное слово. Соответствующим конечным состоянием будет q_Y. Язык НДМТ - множество слов, принимаемых хотя бы одной ДМТ A(S) из [^(A)]:

[^L]([^А]) := {S О S* | $S О S* :   S О L(А(S))}.

Слова S в определении НДМТ можно проинтерпретировать как подсказки к решению (догадки), тогда ДМТ А(S) проверяет для входного слова S подсказку S и в случае правильности останавливается в состоянии q_Y. НДМТ [^(A)] проверяет для входного слова S все возможные подсказки, и если хоть одна правильная догадка существует, то НДМТ останавливается с ответом ``да". (В силу бесконечности числа догадок, в состоянии q_N НДМТ остановиться не может.)

Определение 3. НДМТ [^А] решает массовую задачу П с кодировкой e,  если L(П,e) = [^L]([^А]), т.е. языки НДМТ и задачи совпадают:
"S О L(П,e) $S О S^*:  ДМТ А(S) останавливается в состоянии q_Y,
и "S О S^* \L(П,e),  "S О S^*  ДМТ А(S) не принимает S (не останавливается или останавливается в состоянии q_N).

Определим "S О [^L]([^А]) время работы НДМТ [^А] над словом S как минимальное из времен работы над входом S ДМТ А(S), принимающих S, с учетом времени прочтения слова S (т.е. его длины):

^ t   [^(A)]  (S) := min {S| S О LA(S)}  {|S| + tA(S) (S)}.

Временн'ой сложностью НДМТ [^А] решения массовой задачи П назовем функцию [^T]_[^(A)](·):    "n О Z₊

^ T   [^(A)]  (n) = max S О [^L]([^А]): |S| < n   ^ t   [^(A)]  (S)= max S О [^L]([^А]): |S| < n    min {S|S О LA(S)}  {|S| + tA(S) (S)}.

Подчеркнем разницу с определением временн'ой сложности ДМТ: для НДМТ рассматриваются лишь слова из языка (соответствующие индивидуальным задачам с ответом ``да").

Определение 4. Класс недетерминированно полиномиальных задач NP := {L(П,e)| $[^А] - НДМТ, решающая П с кодировкой e,  $p(·) - полином:   [^T]_[^(A)](n) < p(n)    "n О Z₊}. Если для задачи П существует такая кодировка e, что L(П,e) О NP, то будем называть задачу П недетерминированно полиномиальной и пользоваться обозначением П О NP (как и для класса P, корректным).

Примером недетерминированно полиномиальной задачи является КМ, ибо в качестве догадки можно использовать маршрут и проверка его допустимости полиномиальна.

Отметим, что полиномиальность проверки гарантируется только для индивидуальных задач с ответом ``да" (и возможно, лишь при единственной подсказке), а для I О D(П) \Y(П)  НДМТ просто не остановится. В этом - существенное отличие классов P и NP. Непосредственно из определений следует

Утверждение 1.  P Н NP.

Вопрос о наличии строгого включения и является формализацией основной проблемы теории сложности.

§ 2. NP-полные (универсальные) задачи

Теорема об экспоненциальной оценке временн'ой сложности для задач из класса NP. Класс со-NР. Задачи, имеющие хорошую характеризацию. Определение полиномиальной сводимости. Класс NPC. Теорема Кука (без доказательства). Критерий NP-полноты. Доказательство NP-полноты задачи БЛH (булевы линейные неравенства).

1. Рассмотрим подробнее класс NP.

Теорема 1. Для любой недетерминированно полиномиальной задачи существует ДМТ, решающая ее с экспоненциальной временной сложностью, т.е. "П О NP  $p(·) - полином - и ДМТ А:

А решает П и TА(n) < 2p(n)   "n О Z+.

Доказательство. Так как П О NP, то для любого слова S из языка задачи П существует правильная догадка S полиномиальной длины: |S | < p₁(|S|),  p₁(·) - полином, и существует ДМТ А(S):   t_А(S)(S) < p₂(|S|),  p₂(·) - полином. Построим ДМТ А, которая работает над любым входным словом S О S^* (с любой индивидуальной задачей I О П) следующим образом: рассматриваются все слова S из S^* длины меньше p₁(|S|) и делается не более p₂(|S|) шагов с каждой ДМТ А(S). Если очередная ДМТ останавливается в состоянии q_Y (т.е. соответствующая догадка оказалась правильной), считаем слово S принятым и работу ДМТ А законченной; если ни одна из ДМТ А(S) не остановилась за отведенное время или остановилась в состоянии q_N, то заканчиваем работу ДМТ А и приписываем ей конечное состояние q_N. В последнем случае ДМТ А делает наибольшее число шагов, и это число меньше p₂(|S|)·|S|^p₁(|S|) (второй сомножитель равен числу проверяемых догадок,  |S|  - число символов в алфавите S). Отсюда уже нетрудно получить утверждение теоремы.

Для того чтобы лучше почувствовать различие классов P и NP, введем понятие дополнительной к П массовой задачи [`П], получающейся из П распознавания свойств заменой альтернативного вопроса, определяющего ответ в задаче (см. п.2<sup>0</sup> определения П в §1) его отрицанием, например вопросом в [`КМ]  ``правда ли, что не существует маршрута длины, не превосходящей B?". Формально D([`П]) = D(П),   Y([`П]) = D(П) \Y(П).

Определим классы дополнительных задач co-P := {[`П] | П О P} и co-NP := {[`П] | П О NP}. Из определений очевидно, что, если ДМТ А решает П, то ДМТ [`А] решает [`П], где программа ДМТ [`А] получена из программы ДМТ А простой заменой конечных состояний q_Y и q_N друг на друга. Таким образом, справедливо

Утверждение 2.  co-P = P.

Аналогичное утверждение для класса NP до сих пор не удается ни доказать ни опровергнуть: приведенное выше для ДМТ рассуждение нельзя обобщить на НДМТ, ибо для индивидуальных задач I с ответом ``нет" (т.е. I П Y(П), или I О Y([`П])) НДМТ не останавливается за время, ограниченное полиномом от длины входа I. В частности, не известна НДМТ, решающая [`КМ] за полиномиальное время, так как для нее не придумано подсказки полиномиальной длины (естественный вариант - показать все маршруты - не полиномиален); включение [`КМ] О NP не доказано и не опровергнуто.

УПРАЖНЕНИЕ 3. Доказать, что задача распознавания простоты числа принадлежит классу со-NР, т.е. [`ПЧ] О NP.

Определение 5. Массовая задача распознавания свойств называется имеющей хорошую характеризацию, если для нее выполнено П О NP Зco-NP.

Из утверждения 2 следует, что P Н NP Зco-NP. Современная гипотеза состоит в равенстве этих классов. Отсюда и термин ``хорошая характеризация", так как для подобных задач есть основания надеяться на возможность построения полиномиальных алгоритмов (см. задачу ЛН - линейные неравенства - в разд.2). Однако для задачи ПЧ, обладающей хорошей характеризацией (для доказательства того, что ПЧ О NP, см. [2, с. 414]), детерминированного полиномиального алгоритма пока не найдено, несмотря на ее непосредственную практическую значимость.

2. Задач распознавания свойств - большое разнообразие, и для теории представляет интерес не только возможность их классификации, но и способы определения класса сложности одних задач на основе известного класса сложности других. Поэтому вводится базовое для теории сложности понятие полиномиальной сводимости.

Определение 6. Будем говорить, что массовая задача распознавания свойств Пў с кодировкой eў полиномиально сводится к задаче П с кодировкой e, если любая индивидуальная задача Iў О Пў может быть сведена за полиномиальное время к некоторой I О П с сохранением ответа. Формально

существует функция сводимости f: eў(D (Пў)) ® e(D (П)), такая что   f(eў(Y (Пў))) = e(Y (П)), т.е. "Sў О eў(Y (Пў)) f(Sў) О e(Y (П)) и "Sўў О eў(D(Пў)\Y (П))  f(Sўў) О e(D(П)\ Y (П)),

и существует ДМТ A_f,  реализующая f за полиномиальное время, т.е. $p_f(·) - полином:   "S О eў(D(Пў))   T_Af (|S|) < p_f(|S|).
В случае, когда соответствующие кодировки не избыточны, будем использовать термин полиномиальной сводимости по отношению к самим задачам (без указания кодировок) и применять обозначение

Пў µ П.

(Корректность упрощения вытекает из полиномиальной сводимости задачи к самой себе, но с другой неизбыточной кодировкой, и следующего очевидного утверждения - транзитивности отношения µ .)

Утверждение 3. Если П₁ µ П₂  и П₂ µ П₃,  то П₁ µ П₃.

Существенным для теории сложности является

Утверждение 4. Если Пў µ П  и П О P,  то и Пў О P.

Доказательство. Обозначим А ДМТ, решающую П с полиномиальной временной сложностью, и построим ДМТ Aў, решающую Пў с полиномиальной временной сложностью, как суперпозцию ДМТ A и A_f:  Aў = A°A_f,  т.е. сначала к любому входному слову Sў О eў(D(Пў))  применяется A_f,  а потом к получившемуся слову S = f(Sў)  (длиной не более p_f(|Sў|)) применяется A. Временная сложность Aў - T_Aў(·) Ј T_Af(·) + T_A(p_f(·)) - полином.

Аналогично доказывается (при замене слова ДМТ на НДМТ)

Утверждение 5. Если Пў µ П  и П О NP,  то и Пў О NP.

Определение 7. Массовая задача П называется NP-полной или универсальной, если П О NP  и "Пў О NP   Пў µ П (т.е. любая недерминированно полиномиальная задача полиномиально сводится к П). Класс всех NP-полных задач (распознавания свойств) обозначается NPC (NP-complete).

Непустоту класса NPC доказал С. А. Кук в 1971 г. Им была рассмотрена задача о выполнимости (ВЫП): выяснить выполнимость конъюнктивной нормальной формы (КНФ) - конъюнкции конечного числа дизъюнктивных функций, т.е. дизъюнкций булевых переменных z_i или их отрицаний [`(z_i)]. А именно, в задаче ВЫП требуется распознать для КНФ на входе, существует ли выполняющий набор z⁰ (для которого значение КНФ равно 1).

Теорема 2 (S. A. Cook).  ВЫП О NPC.

Доказательство полиномиальной сводимости к ВЫП любой недетерминированно полиномиальной задачи основано на формальной записи условия принадлежности слова S языку из класса NP (того, что S принимается некоторой НДМТ, а значит, и какой-то ДМТ) в виде набора дизъюнктивных функций от специально вводимых булевых переменных, связанных с состояниями ДМТ в различные моменты времени, и является недостаточно простым для вводного курса (см. [1,2]). Поэтому мы лишь убедимся в том, что ВЫП О NP. Действительно, входное слово (параметры, определяющие индивидуальную задачу выполнимости) содержит число дизъюнктивных функций в КНФ и указание для каждой из них, какие переменные входят с отрицанием, а какие не входят вообще. Длину такого слова можно ограничить снизу суммой длин дизъюнктивных функций, понимая под длиной функции число ее переменных (или число знаков дизъюнкции + 1). Если теперь в качестве подсказки для определяемой входным словом КНФ взять z⁰ - выполняющий ее набор, то вычисление на нем значения КНФ (проверка выполнимости) потребует такого же по порядку числа шагов.

Из определения NP-полноты непосредственно следует

Утверждение 6.  Если P ЗNPC № Ж, то P = NP.  А если
NPC З(NP\P) № Ж, то NPC Н NP\P.

Таким образом, если бы удалось найти полиномиальный алгоритм решения хоть одной NP-полной задачи, то были бы построены полиномиальные алгоритмы решения всех NP-полных задач и всех задач из класса NP, а если для какой-либо NP-полной задачи доказать отсутствие полиномиального алгоритма ее решения, то это не только дает строгое включение P М NP (т.е. ответ к основной проблеме теории сложности), но и влечет за собой доказательство невозможности построения полиномиального алгоритма решения любой задачи из класса NPC. Поскольку ни того, ни другого пока не сделано, считается, что задачи из NPC отвечают житейскому представлению о трудной задаче и вряд ли допускают эффективное решение. Поэтому, если встречается задача, для которой на практике не удается придумать непереборный алгоритм, то имеет смысл попытаться доказать ее NP-полноту, чтобы оправдать применение к ней тех или иных переборных схем.

3. После того как была установлена непустота класса NPC (теоремой Кука), появилась возможность доказательства NP-полноты массовой задачи П путем полиномиального сведения к П одной из известных NP-полных задач (соответствующий список см. в [1]). Действительно, из утверждения 3 следует

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

{П О NPC}  Ы  {П О NP  и   $Пў О NPC:   Пў µ П}.

Пользуясь теоремой 3, можно показать NP-полноту задачи о существовании целочисленного решения системы линейных неравенств с целыми коэффициентами (ЦЛН).

Утверждение 7. ЦЛН О NPC.

Доказательство. 1) ЦЛН О NP, так как подсказкой может служить решение системы, а его проверка сводится к умножению на заданные коэффициенты и сложению, что не превосходит полинома от длины записи всех коэффициентов (доказательство полиномиальности длины записи решения см. в [2, с. 330]).

2) ВЫП µ ЦЛН. Общий вид системы линейных неравенств

              a_j1z₁ + a_j2z₂ + ј+ a_jnz_n Ј b_j,    j = 1,ј,m.
Нетрудно представить в подобной форме условие истинности дизъюнктивной функции. Для этого заменим в каждой j-й функции знаки дизъюнкции знаками суммы, а отрицания переменных z_i - на (1-z_i) и напишем для получившейся линейной функции условие і 1, добавив ограничения z_i і 0 и z_i Ј 1 на все переменные. Целочисленное решение z⁰ = { z⁰_i} системы всех построенных неравенств является выполняющим набором для исходной КНФ (так как истинность КНФ эквивалентна истинности всех образующих ее дизъюнктивных функций). Таким способом решение любой индивидуальной задачи о выполнимости сводится к решению некоторой индивидуальной задачи I О ЦЛН. Полиномиальность сведения очевидна.

Заметим, что фактически в п.2 данного доказательства доказан более сильный результат о сведении ВЫП к подзадаче ЦЛН - задаче о существовании булева решения системы линейных неравенств с целыми коэффициентами (БЛН). Доказательство принадлежности БЛН классу недетерминированно полиномиальных задач повторяет п.1 данного доказательства без ссылки на [2] (так как полиномиальность длины булева решения очевидна), тем самым получено и

Утверждение 8.  БЛН О NPC.

§ 3. Классы сложности.

Сильная NP-полнота и псевдополиномиальность

Доказательство NP-полноты задачи о 3-выполнимости. Взаимоотношение классов Р, NР и NРС, NР и со-NР. NP-трудные задачи. Класс РSРАСЕ. Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке. Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения.

1. Кроме задачи о выполнимости, NP-полнота всех остальных известных задач из класса NPС (в том числе и КМ) была доказана на основе теоремы 3 с помощью полиномиального сведения. Общие рецепты доказательства полиномиальной сводимости (см. в [1]) легко использовать лишь в простейших случаях. Чтобы научиться их применять, надо разобрать большое число примеров (в частности, имеющиеся в [1,2]), на что у нас в рамках данной работы нет возможности. Однако, еще один пример будет далее приведен с целью показать, что не только любая подзадача сводится к соответствующей задаче (автоматически), но возможно и обратное сведение.

Рассмотрим частный случай задачи о выполнимости, когда в КНФ могут входить лишь дизъюнктивные функции трех переменных (3-ВЫП). Поскольку D(3-ВЫП) М D(ВЫП), то по определению 3-ВЫП µ ВЫП. Так что 3-ВЫП О NP (по утверждению 5). Но ее NP-полнота требует специального доказательства, ибо частные массовые задачи содержат меньше индивидуальных задач и могут оказаться проще; например, аналогичная задача 2-ВЫП полиномиальна. Для получения результата 3-ВЫП О NPС докажем, что NP-полная задача о выполнимости сводится к своей подзадаче (частному случаю) 3-ВЫП.

Утверждение 9.  ВЫП µ 3-ВЫП.

Доказательство. Покажем, что произвольную дизъюнктивную функцию f^j(z^j)  k переменных можно представить в виде конъюнкции дизъюнктивных функций от трех переменных (за счет введения дополнительных переменных u^j). Обозначим через y_i переменную z_i^j или [`z]<sub>i</sub><sup>j</sup> в зависимости от того, как i-я компонента z<sup>j</sup> входит в рассматриваемую дизъюнктивную функцию; тогда последнюю можно записать как  y<sub>1</sub> Ъy<sub>2</sub> ЪјЪy<sub>k</sub>  и при k > 3 заменить на КНФ:
(y<sub>1</sub> Ъy<sub>2</sub> Ъu<sup>j</sup><sub>1</sub>) & (y<sub>3</sub> Ъ[`(u^j₁)]Ъu^j₂) & (y₄ Ъ[`(u^j₂)] Ъu^j₃) & ј

ј& (y_k-2 Ъ[`(u<sup>j</sup><sub>k-4</sub>)] Ъu<sup>j</sup><sub>k-3</sub>)& (y<sub>k-1</sub> Ъy<sub>k</sub> Ъ[`(u^j_k-3)]).

Отметим, что данная замена не является эквивалентной. Действительно, если исходная дизъюнктивная функция равнялась нулю, то построенная КНФ равна нулю при всех значениях u, но если исходная дизъюнктивная функция равнялась 1, то найдется такое значение u, чтобы КНФ равнялась 1. Этого, однако, достаточно для сохранения ответа на вопрос о существовании выполняющего набора.

УПРАЖНЕНИЕ 4. Завершить доказательство NР-полноты задачи 3-ВЫП (рассмотреть случаи k < 3).

2. Универсальность задач из класса NPС (NP-полных задач) состоит в том, что основные нерешенные вопросы для класса NP (недетерминированно полиномиальных задач) достаточно разрешить хотя бы для одной NP-полной задачи, чтобы получить ответ для всего класса NP. Кроме утверждения 6 здесь также важно

Утверждение 10. Если для некоторой NP-полной задачи П дополнительная к ней [`П] принадлежит классу NP, то NP = co-NP.

Доказательство. Так как П О NPC, то "Пў О NP  Пў µ П, отсюда и [`П]ў µ [`П] (полиномиальное сведение осуществляется той же функцией - см. определение 6). Но [`П] О NP, значит, [`П]ў О NP по утверждению 5. С учетом произвольности Пў О NP  получили, что co-NP Н NP. Обратное включение доказывается на основании очевидного равенства П = [`([`П])].

Напомним, что гипотеза NP = co-NP в настоящее время кажется нереальной (реальная гипотеза P = NPЗco-NP), и вряд ли для какой-либо NP-полной задачи удастся доказать принадлежность классу co-NP. Поэтому для конкретной недерминированно полиномиальной массовой задачи П О NP, если ее решение представляет интерес, имеет смысл попытаться доказать включение [`П] О NP (т.е. ее хорошую характеризацию) и затем построить полиномиальный алгоритм решения, либо, когда указанное включение не доказывается, надо попробовать полиномиально свести к П одну из известных NP-полных задач (т.е. показать NP-полноту П) и в случае успеха подыскивать переборную схему решения (учитывая ограничения на размерность практически решаемых индивидуальных задач).

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

1) П распознавания свойств, для которых доказано, что Пў µ П для Пў О NPC, но не показано, что П О NP (в частности, это задачи П О co-NPC);

2) П оптимизации, для которых соответствующие П распознавания свойств NP-полны (например, задача коммивояжера из п.1 § 1);

3) и остальные массовые задачи (не обязательно распознавания свойств), к которым сводятся по Тьюрингу какие-либо NP-полные задачи Пў О NPC, где сводимость по Тьюрингу - Пў µ _T П - означает, что из существования полиномиального алгоритма решения П следует существование полиномиального алгоритма и для Пў.

Задачи П (не обязательно распознавания свойств), для которых $Пў О NPC:  Пў µ _T П и $Пўў О NP:  П µ _T Пўў, называются задачами из класса NP-эквивалентных.

Все рассмотренные нами классы задач П - классы сложности  включаются в общий класс PSPACE массовых задач (не обязательно распознавания свойств), для решения которых существуют алгоритмы, требующие не более чем полиномиальной памяти. Вопрос о равенстве P и PSPACE является открытым. Рабочая гипотеза состоит в наличии строгого включения P М PSPACE, при этом NP-полные, NP-трудные и NP-эквивалентные задачи должны включаться в PSPACE\P. (Соответствующую диаграмму взаимосвязи классов сложности см. в [2, с. 412].)

Заметим, что теоретически рассмотренную схему построения классов сложности можно применять и для других схем классификации; в частности, вводят также класс PSPACE-полных задач (к которым полиномиально сводится любая задача из класса PSPACE). Кроме полиномиальной сводимости можно аналогично говорить о логарифмической сводимости, о задачах, требующих логарифмической памяти и т.п. В настоящее время наиболее интенсивно изучаемым здесь оказывается класс NC (Nick Class, автор N. Pippenger) задач, решаемых за время, ограниченное полиномом от логарифма длины входа, и требующих полиномиальной памяти (логарифмическое время при возможности полиномиального числа процессоров). К сожалению, изложение полученных для NC результатов выходит за рамки введения в теорию сложности.

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

Рассмотрим самую простую (по формулировке) NP-трудную задачу - задачу о рюкзаке (ЗР), заключающуюся в том, чтобы из имеющегося набора полезных вещей собрать рюкзак ограниченного объема с наибольшей пользой. Формально требуется найти

max z: zj О {0,1} "j = 1,ј,n  { n е j = 1  cj zj |  n е j = 1  wj zj Ј K },

где c_j О Z₊ - полезность (ценность), w_j О Z₊ - объем (вес) j-й вещи, а переменная z_j определяет класть или не класть ее в рюкзак; максимально возможный объем (вес) рюкзака задается параметром K О Z₊. Соответствующая задача распознавания свойств - существует ли булево решение системы двух линейных неравенств

n е j = 1  cj zj і B  и   n е j = 1  wj zj Ј K

с натуральными коэффициентами - NP-полна (доказательство не следует из утверждения 8, так как рассматривается частный случай БЛН, поэтому см. [1, с. 87 или 2, с. 386]). Для решения ЗР известен следующий метод (динамического программирования).

Произвольная индивидуальная задача I О ЗР погружается в семейство задач поиска

Fi(E) := max z: zj О {0,1} "j = i,ј,n  { n е j = i  cj zj |  n е j = i  wj zj Ј K-E },

F₁(0) - значение ЗР. И решаются все задачи данного семейства по рекуррентным формулам, где i убывает с n до 1. А именно, положим F_i(E):= 0  "E і K,  "i.  Имеем  "E = [`(0,K-1)]:

Fn(E) = м н о 0, E > K-wn, cn иначе,

и  "i = n-1, ј,2:   F_i(E) = max{F_i+1(E), c_i + F_i+1(E+w_i)}:=

:= max zi О {0,1}  {ci zi + Fi+1 (E+wi zi)};  F1(0) = max {F2(0), c1 + F2(w1)}.

Число итераций предложенного алгоритма равно nK и того же порядка будет его временн'ая сложность. Отметим, что алгоритм не является полиномиальным, ибо для записи числа K требуется порядка log₂ K символов; он также оказывается переборным - перебирает все варианты заполненности рюкзака. Однако при не очень больших объемах рюкзака можно довольно быстро получить решение. Для обобщения указанного свойства дадим

Определение 8. Обозначим через num(I) максимальное по модулю целое число (или 0), фигурирующее при задании числовых параметров для индивидуальной задачи I, и через |I|:= |e(I)| - длину записи I. Алгоритм А решения массовой задачи П (не обязательно распознавания свойств) называется псевдополиномиальным, если для некоторого полинома p(·,·) выполнено T_A(|I|) < p(|I|,num(I)).

Примером псевдополиномиального алгоритма является алгоритм динамического программирования для решения ЗР. Для многих других задач (в частности, КМ) псевдополиномиальных алгоритмов не известно. Чтобы выделить класс таких задач, введем понятие полиномиального сужения массовой задачи П как множества тех индивидуальных задач, числовые параметры которых не превосходят полинома от длины входа,

Пp(·):= {I О П| num(I) < p(|I|)}.

Определение 9. Массовая задача П распознавания свойств называется сильно NP-полной, если ее полиномиальное сужение NP-полно, т.е. $p(·) - полином:  П_p(·) О NPC.

Примерами сильно NP-полных задач являются ВЫП и 3-ВЫП (как совпадающие со своими полиномиальными сужениями), БЛН (поскольку ВЫП была сведена к ее полиномиальному сужению, в котором модули правых частей не превышают n), ЦЛН (как обобщение БЛН в отличие от ЗР), а также КМ [1, с. 123-124].

Теорема 4. Если P № NP, то ни для какой сильно NP-полной задачи не существует псевдополиномиального алгоритма решения.

Доказательство проведем от противного. Пусть ДМТ А решает сильно NP-полную задачу П и T_A(|I|) < pў(|I|,num(I)) для полинома pў(·,·). Тогда "I О П_p(·)  T_A(|I|) < pў(|I|,p(|I|)) = pўў(|I|), т.е. П_p(·) О P - противоречие с П_p(·) О NPC или утверждением 6.

Сильно NP-полные задачи считаются наиболее трудными для счета среди всех задач класса NP. Далее мы покажем, что для подобных задач в оптимизационной постановке отсутствуют эффективные алгоритмы поиска даже приближенного решения. Рекомендуемым подходом к их решению является разбиение на подзадачи Пў: D(Пў) Н D(П),  Y(Пў) = Y(П)ЗD(Пў), анализ сложности подзадач и разработка схем перебора (см. в §§ 10,12) для Пў О NPC. При этом для сильно NP-полных подзадач не удается использовать метод динамического программирования в качестве способа перебора (ибо, по-видимому, реализующие его алгоритмы псевдополиномиальны) и следует ориентироваться на схему метода ветвей и границ (§§ 10,11).

§ 4. Приближенное решение задач

комбинаторной оптимизации

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

Важный класс массовых задач образуют задачи дискретной (комбинаторной) оптимизации. Для оптимизационной постановки задачи П решением каждой индивидуальной задачи I О П является произвольная реализация оптимума

OptП(I):= max z О SП(I)  fП(I,z),

т.е. такая точка z^*(I) О S_П(I), для которой  f_П(I,z^*(I)) = Opt_П(I). Здесь S_П(I) - область допустимых значений дискретной (целочисленной) переменной z,  f_П(I,·): S_П(I) ® Z - целевая функция индивидуальной задачи I оптимизации,  знак max в постановке задачи может быть заменен на min.

Будем обозначать S_S и S_m те компоненты входного слова S = e(I), определяющего параметры индивидуальной задачи I О П, которые задают допустимую область (ограничения задачи) и функцию цели соответственно. Например, для ЗР имеем  f_ЗР(S,z) = бc,zс, S_ЗР(S) = {z = (z₁,ј,z_n)|z_j О {0,1}  "j = [`1,n]  и  бw,zс Ј K}, S_S = (n,w,K) и S_m = c. Здесь и далее знак б·,·с обозначает скалярное произведение векторов.

Определение 10. Алгоритм А называется приближенным алгоритмом решения массовой задачи П оптимизации, если "I О П он находит некоторую точку из допустимой области z_А(I) О S_П(I), принимаемую за приближенное решение. Значение f_П(I,z_А(I)) называется приближенным значением оптимума и обозначается A(I).

Говорить об абсолютной погрешности приближенного алгоритма решения массовой задачи оптимизации (на классе всевозможных индивидуальных задач) не имеет большого смысла, как показывает

Утверждение 11. Если P № NP, то ни для какой константы C > 0 не существует полиномиального приближенного алгоритма А решения ЗР с оценкой |Opt_ЗР(I) - A(I)| Ј C   "I О ЗР.

Доказательство проведем от противного. Пусть найдены такие C и А. Построим алгоритм Аў следующим образом: "I О ЗР домножим все коэффициенты c_j на C+1 - получим индивидуальную задачу Iў О ЗР, к которой применим алгоритм А и разделим полученный ответ на C+1, т.е. Aў(I) = A(Iў)/(C+1). Очевидно, Opt_ЗР(Iў) = (С+1)Opt_ЗР(I) и из полиномиальности алгоритма А вытекает полиномиальность Аў. При этом его точность равна |Opt_ЗР(I) - Aў(I)| = |Opt_ЗР(Iў) - A(Iў) |/(C+1) Ј C/(C+1) < 1, т.е. равна нулю (так как все значения целевой функции целые). Получили полиномиальный алгоритм точного решения ЗР. Проверка Opt_ЗР(I) і B полиномиальна, значит, построили и полиномиальный алгоритм решения ЗР в постановке распознавания свойств, что с учетом универсальности последней противоречит утверждению 6.

Определение 11. Приближенный алгоритм А решения массовой задачи П оптимизации называется e-приближенным алгоритмом решения П для некоторого e > 0, если

"I О П        |OptП (I) - A(I)| |OptП(I)| < e,

т.е. его относительная погрешность не превосходит e.

Для e-приближенных алгоритмов приведем следующий результат [2, с. 439], доказательство которого основано на методе динамического программирования и в данном курсе опускается.

Теорема 5. Пусть для задачи П оптимизации
1) существует псевдополиномиальный алгоритм ее решения;
2) "I О П  |Opt_П(I)| < p₁(|I|,num(I))  и  num(I) < p₂(|I|,Opt_П (I)) для некоторых полиномов p₁(·,·), p₂(·,·);
3) "S = e(I), I О П: параметры S_S, задающие ограничения, и S_m, задающие целевую функцию, не пересекаются, и "z О S_П(S) функция цели f_П(S,z) линейно зависит от параметров S_m;

тогда $p(·,·) - полином:  "e > 0  $ e-приближенный алгоритм A_e решения П с временн'ой сложностью T_Ae (|I|) < p(|I|,1/e).

Теорема 5 справедлива, например, для ЗР (сравните результат с утверждением 11). Набор алгоритмов {A_e}, определенный в теореме 5, называется полностью полиномиальной приближенной схемой (ПППС) решения задачи П оптимизации. Наличие ПППС - лучшее, чего можно ожидать при решении NP-трудных задач. К сожалению, в целом ряде случаев на это нельзя рассчитывать, так как имеется

Теорема 6. Если для П оптимизации соответствующая ей П распознавания свойств является сильно NP-полной и  $pў(·) - полином:  |Opt_П(I)| < pў(num(I))  "I О П, то при условии, что P № NP, для П не существует ПППС.

Доказательство проведем от противного. Пусть ПППС существует. Построим алгоритм Aў следующим образом. Для любой индивидуальной задачи I  Aў вызывает A_e с e = 1/(pў (num(I))+1). Тогда по определению e-приближенного алгоритма A_e  |Opt_П(I) -Aў(I)| < |Opt_П(I)|/(pў(num(I))+1) < pў(num(I))/(pў(num(I))+1) по условию теоремы. Но в левой части полученного неравенства было целое число, которое оказывается равным нулю как неотрицательное, меньшее 1. Таким образом, алгоритм Aў точен, причем T_Aў(|I|) = T_Ae(|I|) < p(|I|,pў(num(I))+1) по определению ПППС. Следовательно, алгоритм Aў псевдополиномиален, что противоречит теореме 4.

Утверждение 12. Если P № NP, то ни для какого e > 0 не существует полиномиального e-приближенного алгоритма решения оптимизационной постановки задачи коммивояжера.

Доказательство см. в [2, с. 440-441].

Для частного случая КМ, в котором функция d(·,·) расстояния между городами удовлетворяет неравенству треугольника, наиболее точным из известных e-приближенных полиномиальных алгоритмов решения КМ оптимизации является 0.5-приближенный алгоритм Кристофидеса [2, с. 429-432].

Продолжение