Введение

В первой части этой статьи (см.[1]) было рассказано об основных идеях современной теории сложности дискретных задач - теории Кука- Карпа. Содержание этой теории в предельно сжатой форме можно охарактеризовать так.

Рассматривается широкий класс NP дискретных задач, для решения которых может быть использован универсальный, но малоэффективный из-за высокой трудоемкости алгоритм прямого перебора. Для относительно небольшого числа задач из NP удалось придумать эффективные, то есть полиномиальные по трудоемкости, алгоритмы; эти задачи образуют класс P. Для другой, весьма значительной части задач показано, что они являются максимально сложными в NP; такие задачи названы NP-полными. NP-полные задачи объединяет то, что, во-первых, для каждой из них неизвестен полиномиальный алгоритм, и, во-вторых, из полиномиальной разрешимости любой из них следовала бы полиномиальная разрешимость остальных.

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

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

1. Постановка вопроса

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

Выделим в этих фразах слова "различие между задачами", чтобы связать с ними дальнейший рассказ. Если согласиться с тем, что затронутая проблема исключительно трудна и важна, а так считают практически все специалисты, можно попытаться обнаружить признак, не обязательно характеризующий напрямую сложность задач, но отличающий полиномиально разрешимые задачи от NP-полных. Ясно, что этот признак следует искать в конструкциях, связанных с задачами. Одной из таких конструкций, попавших в поле зрения исследоваателей, является многогранник задачи. И прежде чем обратиться к ассоциированным с задачами многогранникам, поговорим немного о многомерных выпуклых многогранниках вообще.

2. Выпуклые многогранники

Обозначим, как обычно, через R^m евклидово m-мерное пространство, элементы которого x = (x₁,..., x_m) называются точками, или векторами. Операции сложения и умножения на число определяются в R^m формулами: x + y = (x₁ + y₁,... x_m + y_m ), αx = (αx₁,..., αx_m ), а величина (x,y) = x_i y_i называется скалярным произведением векторов x и y. Выпуклой комбинацией точек x₁,..., x_s называется точка α₁x₁+...+α_sx_s , где αi - неотрицательные числа, сумма которых равна единице. Выпуклая оболочка convX множества X ? R^m определяется как совокупность всех выпуклых комбинаций точек из X . В том случае, когда X конечно, convX называется выпуклым многогранником. Если при этом каждая точка множества X не является выпуклой комбинацией остальных, то точки из X и только они служат вершинами многогранника M = conv X .

Любой выпуклый многогранник можно определить иначе - в виде множества решений некоторой системы линейных неравенств: M = {x R^m: (a_i, x) C_i; i = 1,..., k} ; этот факт известен как теорема Вейля-Минковского.

Пусть M - некоторый многогранник, X - множество его вершин. Две вершины x,y X называются смежными, если отрезок [x,y] (то есть выпуклая оболочка пары {x, y}) не пересекается с выпуклой оболочкой остальных вершин. Проще, смежность вершин x и y означает, что отрезок [x,y] является ребром многогранника M.

К изучению выпуклых многогранников приводят многие задачи, в числе которых особенно важные в прикладном отношении задачи линейного программирования. В случаях, когда размерность m пространства мала: m 3, анализ геометрических конструкций, и в том числе многогранников, в значительной степени упрощается благодаря возможности "увидеть" объект изучения. Но уже при m = 4 роль этого фактора существенно снижается. И именно здесь, сразу за пределами видимости происходят удивительные вещи, которые можно обнаружить аналитическими методами. Один из таких "ненаглядных" фактов оказывается важным в связи с нашими рассмотрениями.

Зададимся вопросом, сколько попарно смежных вершин может быть у выпуклого многогранника в R^m . При m, равных 2 и 3, ответ почти очевиден: не более трех в R² и не более четырех в R³ (соответственно, для треугольника и для тетраэдра).

Теорема 1. Для любого натурального n в R⁴ существует выпуклый многогранник с n попарно смежными вершинами.

Доказательство. Рассмотрим в R⁴ множество точек ? = {(t, t², t³, t⁴) : t R} ; (индексы сверху - показатели степени). Это множество называется циклической кривой. Пусть x = (?,?2,?3,?4) и y = (?,?2,?3,?4) - две произвольно выбранные точки на этой кривой, здесь ? ? ? . Определим многочлен четвертой степени формулой: ?(t) = (t - ?)2(t - ?)2 . Очевидно, что ?(?) = ?(?) = 0 и ?(t) > 0 , если отлично от ? и от ? . (1) Преобразуем: ?(t) = t⁴ - 2(?+?)t³ + (?2+4??+?2)t² - 2??(?+?)t + ?2?2 и рассмотрим в R⁴ гиперплоскость H = {c R⁴: (a,c) = ?}, где a = (1, -2(?+?), ?2+4??+?2, -2??(?+?)) , ? = -?2?2 . Она разбивает R⁴ на два полупространства, одно из которых H+ = {c R⁴: (a,c) > ?}. Условия (1) означают, что выбранные точки x и y кривой ? принадлежат гиперплоскости H, а остальные точки кривой лежат в H+.

Пусть теперь n - произвольно выбранное натуральное число. Рассмотрим n различных точек кривой ? : x₁,..., x_n , и обозначим M = conv {x₁,..., x_n} . По доказанному, для любых двух вершин x_i и x_j этого многогранника найдется гиперплоскость H, в которой лежат эти вершины, а остальные находятся в H+. Так как H и H+ - выпуклые множества, не имеющие общих точек, отрезок [x_i,x_j] не пересекается с выпуклой оболочкой остальных вершин, то есть x_i и x_j - смежные вершины. Теорема доказана.

Доказанное утверждение имеет любопытную историю. Впервые оно было установлено и опубликовано в 1907 году немецким математиком К.Каратеодори, но осталось незамеченным. Спустя много лет, в 1956 году этот результат появляется в статье американского математика Д.Гейла и приобретает широкую известность благодаря линейному программированию, которое в то время интенсивно развивалось. В дальнейшем на его основе были открыты фундаментальные факты современной теории выпуклых многогранников; подробнее об этом можно прочитать в книге [2].

3. Многогранники задач

Многие дискретные задачи естественным образом приводятся к геометрическому виду, и это дает возможность алгоритмические свойства задач интерпретировать в терминах понятий геометрии. Такая возможность в первую очередь характерна для дискретных задач оптимизации, их часто называют задачами комбинаторной оптимизации; именно о них будет идти речь далее. Большинство задач комбинаторной оптимизации объединяет то, что их можно рассматривать как задачи отыскания минимума (или максимума) линейной функции на конечном множестве точек в пространстве R^m. Как осуществляется этот переход, достаточно общим образом можно продемонстрировать на примере задачи коммивояжера.

Предположим, что расматривается задача коммивояжера для n пунктов, которые занумерованы числами от 1 до n . Обозначим через m количество пар этих пунктов: m = n(n-1)/2, и координаты точек x в пространстве R^m поставим в соответствие парам пунктов: x = (x_ji: 1 i < j n). Для каждого замкнутого маршрута z, включающего все n пунктов, рассмотрим его характеристический вектор x = x(z), полагая 1, если z непосредственно соединяет пункт i с пунктом j , x_ij(z) = 0 в противном случае. Таким образом в пространстве R^m будет определено множество X , состоящее из (n-1)!/2 точек, координаты которых равны нулю или единице.

Предположим теперь, что заданы расстояния c_ij между пунктами; их совокупность будем рассматривать в виде вектора из R^m: c = (c_ij:1i< j n). В результате задача коммивояжера приобретает указанный выше вид задачи минимизации по x на множестве X линейной функции (c,x) = c_ij x_ij . (2) Заметим, что в приведенном рассуждении фигурировала индивидуальная задача коммивояжера, задаваемая вектором c расстояний между пунктами. Рассматривая всевозможные с из R^m, мы получим совокупность всех индивидуальных задач коммивояжера для n городов, то есть массовую задачу. Последнюю естественно обозначить через X - так же, как и множество, на котором минимизируются линейные функции (2), различающиеся для разных индивидуальных задач лишь коэффициентами c_ij.

К описанному виду совершенно аналогично приводится задача задача о минимальном остовном дереве и многие другие.

Пусть X - некоторая задача, X ? R^m. Рассмотрим две геометрические конструкции, связанные с X.

Обозначим через M(X) выпуклую оболочку множества X : M(X) = conv X, и назовем ее многогранником задачи X . Без ограничения общности можно считать, что множество вершин многогранника M(X) совпадает с X .

Зафиксируем x X и определим множество K(x) = {cR^m: (c,x)?(c,y) при любом yX}. Оно представляет собой многогранный конус и состоит из тех точек cR^m, для которых решением соответствующих индивидуальных задач служит x. Сама же индивидуальная задача, задаваемая вектором c, заключается в отыскании такого x X, для которого c K(x).

Для многогранника M(X) задачи и множества конусов K(x), x X, легко устанавливается простая связь.

Теорема 2. Конусы K(x) и K(y) имеют общую гипергрань (то есть грань размерности m-1) в том и только том случае, если x и y - смежные вершины многогранника M(X).

Немного отвлекаясь от основной темы, заметим, что последнее утверждение приводит к весьма неожиданному факту элементарной геометрии. Пусть X - конечное множество точек циклической кривой ? в R⁴. Из доказанной ранее теоремы 1 и из теоремы 2 вытекает, что любые два конуса K(x) и K(y), где x,y X, имеют общую трехмерную грань. Рассмотрим в R⁴ симплекс S = {x = (x₁,x₂,x₃,x₄): x₁+x₂+x₃+x₄= 1, x_i ?0 , i = 1,2,3,4}; его размерность равна трем. Обозначим Q(x) = K(x)?S, x X. Эти множества являются трехмерными выпуклыми многогранниками, каждые два из которых имеют общую двумерную грань, но не содержат общих внутренних точек. Учитывая, что исходное множество X могло состоять из любого количества точек, приходим к следующему результату.

В пространстве R³ можно построить произвольно много выпуклых многогранников без общих внутренних точек, каждые два из которых имеют общую плоскую грань.

4. Плотность полиэдрального графа задачи

Продолжим разговор о геометрических конструкциях, связанных с задачами комбинаторной оптимизации. Обозначая, как и ранее, через X некоторую задачу, X ? R^m, рассмотрим граф G(X) многогранника M(X); множеством вершин этого графа служит X , а ребрами являются геометрические ребра многогранника. Граф G(X) называется полиэдральным графом задачи X . Обозначим через p(X) максимальное количество попарно смежных вершин графа G(X), эта характеристика графа называется его плотностью.

Плотность полиэдрального графа задачи оказывается именно той величиной, поведение которой отражается на степени труднорешаемости задачи. В основе этой зависимости находится следующая интерпретация величины p(X), непосредственно вытекающая из теоремы 2.

Теорема 3. Значение p(X) равно максимальному количеству таких точек из X, что для любых двух x и y из них соответствующие конусы K(x) и K(y) имеют общую гипергрань.

Ниже, где речь пойдет о геометрических свойствах алгоритмов, роль теоремы 3 проявится более определенным образом. Сейчас же остановимся на результатах исследований, связанных с оценками плотности полиэдральных графов для известных задач.

До сих пор рассуждения проводились в предположении, что размерность m пространства R^m фиксирована. Теперь обратим внимание на то, что понятие "задача" приводит к рассмотрению последовательности конечных множеств X_m ? R^m, где m может принимать как угодно большие значения. Так, в примере с задачей коммивояжера m = n(n-1)/2 , а число пунктов n - произвольное натуральное. Соответственно, и величина p(X_m) является последовательностью, значения которой меняются в зависимости от m. В большой серии работ, опубликованных в течение последних десяти лет, изучалось поведение плотности p(X_m) полиэдральных графов различных задач комбинаторной оптимизации. В итоге обнаружилась весьма любопытная закономерность: для всех полиномиально разрешимых задач плотность p(X_m) ограничена сверху степенной функцией от m и для каждой NP-полной задачи p(X_m) растет быстрее, чем любая степенная функция. Иначе говоря, p(X_m) полиномиальна для эффективно разрешимых задач и неполиномиальна для труднорешаемых. В частности, для задач, которые обсуждались в настоящей статье, справедливы следующие оценки: - для задачи о минимальном остовном дереве p(X_m) m , - для задачи коммивояжера p(X_m) ? ? 2 , ? = const > 0. Оценки плотности полиэдральных графов других задач можно найти в работе [3].

Таким образом, характер роста величины p(X^m) служит, различающим задачи по сложности, о существовании которого ставился вопрос во введении. Естественно возникает новый вопрос: является обнаруженная зависимость между сложностью задачи и плотностью ее полиэдрадьного графа случайной или имеет теоретическое объяснение. Чтобы попытаться ответить на этот вопрос, нам придется поговорить об алгоритмах.

5. Геометрическая интерпретация алгоритмов

Общее свойство всех алгоритмов комбинаторной оптимизации, которое проявляется даже при поверхностном знакомстве с ними, состоит в том, что выбор оптимального элемента x* в множестве X происходит в результате выполнения конечной последовательности линейных сравнений для вектора c* R^m, задающего индивидуальую задачу. Например, жадный алгоритм, который был приведен в первой части статьи для задачи о минимальном остовном дереве, формирует решение на основе упорядочения расстояний между пунктами, а для упорядочения используются простейшие сравнения этих расстояний между собой. В других алгоритмах, большое количество которых описано в книге [4], применяются и более сложные линейные сравнения, но во всех случаях эти операции заключаются в определении знака линейной формы (f ,c*), где f - некоторый вектор из R^m.

Указанное общее свойство алгоритмов допускает простую геометрическую интерпретацию процедуры решения индивидуальной задачи. Как было отмечено ранее, индивидуальная задача для вектора c* заключается в отыскании такого x* X, для которого c* K(x*). Для этого последовательно в R^m строятся гиперплоскости вида H = {cR^m: (f,c) = 0} (3) и выясняется, какому полупространству - H+ или H- - принадлежит точка c*. Каждый такой шаг позволяет исключить из числа претендентов на оптимальность те точки x X, для которых соответствующие конусы K(x) лежат в другом полупространстве. Процесс завершается, когда исключенными оказываются все, кроме одной, точки из X ; оставшаяся точка x* является решением индивидуальной задачи.

Предположим теперь, что для некоторых p точек из X каждые два конуса K(x) и K(y) имеют общую гипергрань. Предположим также, что точка c* принадлежит одному из этих p конусов, но заранее не известно, какому именно. Рассмотрим в R^m гиперплоскость H вида (3) и образуемые ею полупространства H+ и H- . Тогда справедливо утверждение: хотя бы одно из этих полупространств содержит точки по крайней мере p-1 конусов. (Это утверждение наглядно для R³, правда, в таком случае p не может быть больше четырех, и легко доказывается для произвольного m .) Отсюда следует, что для гарантированного отыскания конуса, который содержит точку c*, потребуется не меньше p-1 шагов описанного выше вида. Если связать этот результат с геометрической интерпретацией алгоритмов и учесть теорему 3, станет понятной роль плотности полиэдрального графа задачи как нижней оценки трудоемкости алгоритмов традиционного типа.

Заключение

Какие выводы можно сделать в итоге ? Можно ли считать, что для задач с высокой плотностью полиэдрального графа не существуют (то есть не могут быть построены) полиномиальные алгоритмы ?

Сразу же заметим, что из нашего рассказа утвердительный ответ на последний вопрос вовсе не следует. Более того, описанная интерпретация традиционных алгоритмов свидетельствует о достаточно примитивном единообразии их в геометрическом смысле, хотя в комбинаторном отношении часто эти алгоритмы вовсе не тривиальны. Поэтому нет смысла преувеличивать значение многолетних безуспешных попыток многих специалистов построить полиномиальные алгоритмы для NP- полных задач. Такие попытки без привлечения принципиально новых геометрических идей заведомо обречены на неудачу. Что же касается новых геометрических идей, следует особо отметить появившиеся относительно недавно полиномиальные алгоритмы для задачи линейного программирования; первый из них построил Л.Г.Хачиян в 1979 году. Геометрическая природа этих алгоритмов совершенно иная по сравнению с традиционными, что определяет их привлекательность в связи с изложенным в данной работе.

Итак, высокая плотность полиэдральных графов, характерная для NP-полных задач, является серьезным препятствием при конструировании эффективных алгоритмов. Учитывая, что среди изученных задач значительное большинство составляют NP-полные, можно сделать следующее предположение. Если в многомерном пространстве случайным образом выбрать конечное множество точек X , то величина p(X) с высокой вероятностью будет принимать большие значения. Это предположение находит теоретическое подтверждение в работе [3]. В частности, при случайном выборе множества X из 25 000 точек, координаты которых равны нулю или единице, в 100-мерном пространстве с вероятностью 0.99 величина p(X) окажется равной количеству точек, то есть 25 000.

Литература

1. Бондаренко В.А. О сложности дискретных задач. Часть 1. Соросовский образовательный журнал (статья направлена в журнал).
2. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация.- М.:Наука, 1981.- 344 с.
3. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации.- Ярославль: Ярославский госуниверситет, 1995.- 126 с.
4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.- М.:Мир, 1985.- 512 с.