Введение

В последнее время стало обычным использование терминов "непрерывные задачи" и "дискретные задачи". Установить строгое различие между этими двумя типами математических задач непросто, да и не представляет особого смысла, так как одна и та же задача может рассматриваться как непрерывная и как дискретная в зависимости от выбора подходов к ее решению. Говоря же грубо, можно считать непрерывными те задачи, в постановке которых фигурируют непрерывные множества, например, R - множество всех действительных чисел и т.п. Для описания дискретных задач используются множества дискретной природы, например, целочисленные множества.

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

1. Примеры дискретных задач

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

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

Задача о минимальном остовном дереве. Здесь исходная ситуация аналогична: имеется n пунктов с заданными целочисленными попарными расстояниями. Требуется спроектировать минимальную по протяженности дорожную сеть без дополнительных узлов, которая позволяла бы из каждого пункта добраться в любой другой.

Задача о составном числе. Для заданного натурального числа z требуется выяснить, является ли оно составным.

Перечень подобного рода задач можно значительно расширить. Но уже приведенные дают основания для обсуждения достаточно характерных общих вопросов. Прежде всего обратим внимание на термин "задача". В тех постановках, которые даны выше, речь идет о массовых задачах, так как предполагается, что в двух первых случаях число пунктов и попарные расстояния между ними могут быть любыми, а в третьей задаче z выбирается также произвольно. Итак, под дискретной задачей мы будем понимать массовую задачу как совокупность индивидуальных задач, соответствующих всевозможным конкретным исходным данным. Примером индивидуальной задачи о составном числе служит такая: выяснить, является составным число 12345678910111213.

2. Алгоритмы

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

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

     Содержательная сторона алгоритма сосредоточена в программе, выполнение которой начинается с подачи входа и завершается формированием выхода. Работа программы осуществляется в виде некоторой последовательности операций, на каждую из которых затрачивается условная единица времени. Характер используемых операций и их последовательность определяются выбором вычислительного устройства, программы и входа. Обозначим через A алгоритм некоторой задачи, через tA(z) - число операций, затрачиваемое алгоритмом A на индивидуальную задачу z, и назовем трудоемкостью алгоритма A функцию TA (L) = max{t A (z): l(z) ? L}. (1) Эта функция характеризует зависимость между длиной входа и временем работы алгоритма. Ясно, что более предпочтительным является такой алгоритм, для которого TA (L) растет как можно медленней.

     Обращаясь теперь к третьему элементу алгоритма - выходу, отметим различие между приведенными выше задачами. Именно, в задаче о составном числе выход предусматривает лишь два варанта: "да" или "нет". Задачи подобного вида называются задачами распознавания. Другие две задачи относятся к классу оптимизационных, или экстремальных, задач.

3. Полиномиальная разрешимость

     Задачи рассматриваемого вида объединяет то, что для решения каждой из них можно использовать простейший алгоритм - алгоритм прямого перебора, который обозначим через S. Попытаемся грубо оценить трудоемкость переборного алгоритма для приведенных выше задач. Для простоты примем, что в первых двух задачах расстояния между пунктами могут принимать целые значения от 1 до 9. Тогда длина l(z) входа индивидуальной задачи z для n пунктов составляет n(n-1)/2. Алгоритм прямого перебора для задачи коммивояжера заключается в вычислении длины каждого кольцевого маршрута и выборе среди них минимального. Общее число обходов n пунктов равно, как легко заметить, (n-1)!/2, и эта величина служит нижней оценкой числа операций при прямом переборе. Учитывая, что l(z) < n2 и tS (z) > 2n при n > 5, можем оценить снизу трудоемкость (1) алгоритма S : TS (L) > 2 при L > 10 . (2)

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

     Проведем аналогичные рассуждения для оценки трудоемкости прямого перебора в задаче о составном числе. В этом случае длина входа l(z) равна количеству цифр в десятичной записи числа z, определяющего индивидуальную задачу, то есть l(z) < lg z + 1. Будем считать, что алгоритм последовательно делит z на натуральные числа, большие единицы и не превосходящие ?z, до тех пор, пока либо остаток не окажется равным нулю, либо не будут исчерпаны указанные числа. В первом случае выходом служит "да", во втором - "нет". Для получения грубой оценки трудоемкости под числом операцией будем понимать количество выполненных делений. Из этих рассуждений следует искомая оценка: TS(L) > 10L/2-1. (3)

     Чтобы сделать полученные оценки более осязаемыми, прикинем объем прямого перебора для входа определенной длины. Предположим, что число n пунктов в первых двух задачах равно 100, то есть l(z) = 50?99 > 702. Из оценки (2) следует, что для решения индивидуальной задачи придется выполнить не менее 10 21 операций. Скорость самых современных ЭВМ не превосходит 1012 операций в секунду. Следовательно, для получения результата придется ждать 109 секунд, или более 30 лет. Оценка (3) приводит к еще более внушительным цифрам. К сказанному можно добавить, что оценки (2) и (3) весьма грубые, действительный рост функции TS (L) более высок; в то же время при проектировании интегральных схем возникают задачи, подобные первым двум, для значений n, значительно превосходящих 100.

     Таким образом, алгоритм прямого перебора, хотя и является универсальным для задач рассматриваемого вида, практически оказывается малоэффективным.

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

     Рассмотрим индивидуальную задачу о минимальном остовном дереве. На первом шаге соединим два пункта, расстояние между которыми минимально. Далее на каждом шаге соединяем ближайшие из оставшихся пар пунктов так, чтобы при этом не появлялось замкнутых маршрутов. Процесс завершаем, когда окажутся соединенными n-1 пар пунктов. Нетрудно показать, что в результате получается искомая дорожная сеть минимальной длины. Описанная процедура легко реализуется в виде алгоритма G, известного под названием "жадный"; его трудоемкость оценивается сверху: TG (L) < L2 . (4) В упомянутом примере для 100 пунктов число используемых операций не превосходит 25000000 и потребует нескольких секунд работы рядового компьютера. Представление об эффективных алгоритмах формализуется следующим определением. Алгоритм A называется полиномиальным, если его трудоемкость удовлетворяет неравенству TA(L) ? ? Lm , где ? и m - не зависящие от L константы.

     Дискретные задачи, для которых существуют полиномиальные алгоритмы, принято называть полиномиально разрешимыми, а их совокупность образует класс P.

     Из трех сформулированных выше лишь задача о минимальном остовном дереве определенно лежит в классе P, это следует из полиномиальности жадного алгоритма. Для двух других задач в настоящее время (1997 г.) полиномиальные алгоритмы неизвестны. В этой связи возникают принципиальные вопросы, привлекшие за последние 30 лет значительное внимание исследователей. Общий смысл этих вопросов заключается в следующем. Пусть для некоторой дискретной задачи не удается сконструировать полиномиальный алгоритм несмотря на серьезные усилия многих математиков (пример - задача коммивояжера). В чем причина этих неудач - в том, что такой алгоритм не существует вовсе, либо полиномиальный алгоритм существует, но найти его очень трудно? Сразу же заметим, что этот вопрос до сих пор остается открытым. Однако попытки найти на него ответ привели четверть века назад к созданию теории труднорешаемых задач, основные результаты которой принадлежат С. Куку [1], Р.Карпу [2] и Л.Левину [3]. Эти результаты оказались в такой мере неожиданными, с одной стороны, и практически важными, с другой, что сама теория сразу же приобрела классический характер и вызвала многочисленные дополнительные исследования и публикации. Наиболее полное изложение этой теории содержится в монографии М.Гэри и Д.Джонсона [4]. Далее в настоящей статье излагаются на содержательном уровне основные элементы теории труднорешаемых задач.

4. Алгоритмы с оракулом и класс NP

     Задачи распознавания даже на первый взгляд представляются более удобными для рассмотрения по сравнению, например, с задачами оптимизации. Для того, чтобы в дальнейшем говорить только о задачах распознавания, коротко остановимся на приведении к этому виду других задач. Для иллюстрации выберем задачу коммивояжера. Близкую к ней задачу распознавания обозначим ЗКР и сформулируем так. Существует ли обход всех пунктов, длина которого не превосходит заданного числа Q? Если предположить существование полиномиального алгоритма для ЗК, то, очевидно, ЗКР тоже полиномиально разрешима. Но верно и обратно:е из того, что ЗКР ? P, следует ЗК ? P. Для доказательства воспользуемся простой идеей известного метода угадывания задуманного числа с помощью вопросов с ответами "да" или "нет". Пусть A - полиномиальный алгоритм задачи ЗКР: TA (L) ? ?L m , и пусть z - индивидуальная ЗК с n пунктами. Искомая длина кратчайшего обхода находится среди чисел n, n+1,..., 9n. Полагая Q = 5n и применяя алгоритм A для соответствующей ЗКР, мы сумеем почти в два раза уменьшить количество чисел - претендентов для выхода в индивидуальной ЗК. Повторив описанную процедуру не более чем log29n + 1 раз, получим решение ЗК. Из неравенства log2 n < n, справедливого при всех натуральных n, вытекает полиномиальность сконструированного алгоритма.

     Итак, класс задач распознавания оказывается достаточно универсальным для изучения вопросов сложности. Далее по словом "задача" будет пониматься именно задача распознавания.

     Пусть Z - некоторая задача. Обозначим через ZY совокупность всех индивидуальных задач, выходом для которых служит "да". Вообразим такую ситуацию. Некто, который знает все, предлагает вам индивидуальную задачу z и утверждает, что z ? ZY . Вы просите доказать это. Можно ли рассчитывать, что всезнающий некто, или оракул, сможет привести достаточно короткое доказательство? Оказывается, во многих случаях можно, даже если задача труднорешаема. Обратимся к нашим примерам. В задаче ЗКР оракул может указать порядок обхода пунктов и остается лишь убедиться, что длина соответствующего замкнутого маршрута не превосходит Q. В другой задаче - о составном числе - оракулу достаточно предъявить делитель числа и продемонстрировать, что остаток равен нулю. Эти примеры могут показаться тривиальными, но если рассмотреть подобную последней задачу о простом числе, то действия оракула уже перестают быть очевидными. На основе сказанного приведем неформальное определение класса задач, которые называются недетерминированно полиномиальными, или класса NP. Будем говорить, что задача Z принадлежит классу NP , если существует описание такого оракула, который доказывает включение z ? ZY алгоритмом полиномиальной трудоемкости. Заметим, что P ? NP , так как алгоритм, решающий задачу Z, можно рассматривать и как алгоритм, устанавливающий включение z ? ZY . Класс NP содержит огромное количество теоретически и практически важных задач, для большинства из них принадлежность классу NP доказывается просто. Ниже речь будет идти в основном о задачах из NP .

5. Сравнение задач по сложности

     Предположим, что рассматриваются две задачи Z и Z' . Попытаемся наполнить смыслом фразу "задача Z не более сложна, чем задача Z'", учитывая при этом, что принципиальным является вопрос о полиномиальной разрешимости. Достаточно естественным представляется следующий вариант. Если из предположения о том, что Z' ? P , следует Z ? P , то принимается, что Z не сложнее, чем Z'. Примером реализации этой идеи может служить рассмотренная выше связь между задачами ЗК и ЗКР. В случае, когда речь идет о задачах распознавания, сравнение их по сложности более формально описывается таким определением. Пусть B - полиномиальный алгоритм, множество входов которого состоит из всех индивидуальных задач z ? Z , а выходами служат z' ? Z', и пусть вход z принадлежит ZY в том и только том случае, когда соответствующий выход z' принадлежит ZY . Тогда говорят, что задача Z полиномиально сводится к задаче Z' ; обозначение: Z ? Z'.

     Для примера покажем, что к задаче Z' = ЗКР полиномиально сводится задача Z о полном пути (Z = ПП); она отличается от ЗКР тем, что в ней речь идет о незамкнутом пути, который проходит через все заданные пункты, начинаясь в каком-либо одном и оканчиваясь в другом пункте. Пусть z - индивидуальная задача о полном пути, в которой количество пунктов равно n, а ограничение на длину пути - Q. Добавим еще один - (n+1)-ый - условный пункт, полагая, что расстояние от него до каждого из n заданных равно единице и Q' = Q + 2, и рассмотрим индивидуальную задачу z' ? ЗКР с n+1 пунктами и ограничением длины обхода, равным Q'. Ясно, что переход от задачи z к задаче z' осуществляется полиномиальным алгоритмом и полный путь, длина которого не превосходит Q, для задачи z существует в том и только том случае, когда для задачи z' существует замкнутый обход всех n+1 пунктов длины, не превышающей Q' .

6. Задачи, самые сложные в классе NP

     Теперь мы можем определить центральное понятие рассматриваемой теории сложности задач.

     Задача Z* называется NP-полной, если Z* ?NP и для любой задачи Z из NP выполняется соотношение: Z ? Z?. Заметим, что приведенное определение приобретает смысл лишь в случае существования хотя бы одной NP-полной, то есть самой труднорешаемой в классе NP, задачи. Оказывается, такие задачи не только существуют, но и составляют большинство задач из NP, для которых не удалось придумать полиномиальные алгоритмы. Обычно для доказательства NP-полноты какой-либо задачи к ней полиномиально сводится другая задача, NP- полнота которой установлена ранее. Исключение в этом отношении, очевидно, представляет та задача, NP-полнота которой была доказана раньше, чем для остальных. Такой чести удостоилась задача ВЫПОЛНИМОСТЬ в знаменитой теореме Кука [1]. Прежде чем сформулировать задачу ВЫПОЛНИМОСТЬ, введем несколько простых понятий, связанных с логическими, или булевскими, функциями. Рассмотрим множество X = {x1, x1 ,..., xn, xn } переменных, каждая из которых может принимать два значения: 0 и 1, причем xi = 1-xi , i = 1,...,n. Подмножество D = {u 1,..., u k} ? X назовем дизъюнкцией. Выберем некоторые значения переменных из X и назовем дизъюнкцию D выполненной, если хотя бы одна ui из D оказалось равной единице.

     Сформулируем теперь задачу ВЫПОЛНИМОСТЬ. Заданы множество X и некоторый набор дизъюнкций Dj ? X, j = 1,...,m. Требуется выяснить, можно ли так выбрать значения переменных xi , i = 1,...,n, чтобы одновременно оказались выполненными все дизъюнкции Dj , j = 1,...,m. ТЕОРЕМА КУКА. Задача ВЫПОЛНИМОСТЬ является NP-полной.

     Привести доказательство этой исключительно важной теоремы в данной статье не представляется возможным, поэтому ограничимся лишь кратким комментарием. Легко понять, что для доказательства полиномиальной сводимости любой задачи из NP к задаче ВЫПОЛНИМОСТЬ необходимо строгое описание класса NP. Это, в свою очередь, связано с формализацией вычислительных конструкций, которые в разделе 4 названы алгоритмами с оракулом. Подходящим аппаратом для такой формализации служат логические функции (в частности - дизъюнкции), они представляют собой математические модели простейших вычислительных элементов, используемых в компьютерах. Сказанным в некоторой степени объясняется тот факт, что задаче ВЫПОЛНИМОСТЬ выпало стать первой обнаруженной NP-полной задачей.

     В настоящее время количество опубликованных NP-полных задач составляет много сотен. Только в книге [4] рассмотрено более трехсот таких задач разнообразного содержания. Можно уверенно утверждать, что каждому, кто имеет дело с дискретными задачами, приходилось сталкиваться с новыми, ранее неизвестными NP-полными задачами. Зачастую полиномиальная сводимость к ним реализуется с помощью весьма хитроумных конструкций, примеры можно найти в книге [4]. Из рассмотренных в данной статье NP-полными наряду с задачей ВЫПОЛНИМОСТЬ являются задачи ЗКР и ПП. Следует сказать и о "неопознанных" задачах - для которых не удалось построить полиномиальный алгоритм и не доказана NP-полнота. Таких задач среди опубликованных относительно немного. Наиболее известна из них задача о составном числе.

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

Заключение

     Попытаемся разглядеть практический смысл затронутых в статье понятий. Представим себя в роли разработчика аклгоритмов, перед которым поставлена новая дискретная задача. Каковы наши действия ? Прежде всего, пороемся в собственной памяти, рассчитывая припомнить что-нибудь подобное, потом - в библиотеке. Если эти поиски закончатся неудачей (ситуация стандартная!), вынуждены будем начать шевелить собственными мозгами в надежде придумать эффективный (то есть полиномиальный) алгоритм. Обладая неограниченной целеустремленностью и будучи не слишком ленивыми, мы можем как угодно долго пребывать в состоянии поиска такого алгоритма. Но благоразумие и знакомство с изложенными в этой статье фактами подскажут иной путь. В случае, когда определенные усилия не приводят к полиномиальному алгоритму, следует попытаться доказать NP-полноту нашей задачи. И если это удастся сделать, надо прекратить все попытки искать полиномиальный алгоритм по причине их значительной безнадежности.

     Правда, остается вопрос: а так ли уж сложны эти самые сложные в NP задачи. Неформально величина сложности NP-полных задач оценивается совокупными умственными затратами многочисленных математиков, безуспешно пытавшихся в течение многих лет до появления теории NP-полных задач конструировать для таких задач полиномиальные алгоритмы. В формальной постановке речь идет о соотношении классов P и NP. Именно, что на самом деле верно: неравенство NP ? P или все-таки равенство между этими классами ? Большинство специалистов склоняются к первому варианту, но в целом вопрос остается открытым и привлекающим значительное внимание исследователей. Аргументированный ответ на этот вопрос явился бы выдающимся математическим результатом.

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

Литература

1. Кук С.А. Сложность процедур вывода теорем. - Кибернетический сборник, новая серия.- 1975.- Вып.12.- С.5-15.
2. Карп Р.М. Сводимость комбинаторных проблем.- Там же. С.16-38.
3. Левин Л.А. Универсальные задачи перебора.- Проблемы передачи информации.- 1973.- Т.9, N 3.- С.115-116.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.:Мир.- 1982.- 416 с.