Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
Теория сложности
Рассуждения о природе, возможности построения, существования и ограничениях алгоритмов, которые я привел в предыдущих главах, были по большей части «нестрогими». Я совсем не касался вопроса о возможности практического применения упоминавшихся алгоритмов. Даже в тех задачах, где существование алгоритмов и возможные способы их построения очевидны, все же может потребоваться довольно много труда для их воплощения в нечто полезное с точки зрения практического использования. Иной раз небольшая догадка или искусный ход могут в значительной степени упростить алгоритм или же многократно увеличить его быстродействие. Техническая сторона этих вопросов часто бывает очень сложна, и в последние годы в различных направлениях прилагалось много усилий в области построения, понимания и совершенствования алгоритмов — быстро растущем и развивающемся поле деятельности для пытливых умов. Мне представляется не слишком уместным углубляться здесь в тонкости подобных вопросов. Однако, существует довольно много абсолютныхограничений общего характера (известных или предполагаемых) на возможное повышение быстродействия алгоритма. Оказывается, что среди алгоритмических по своей природе задач существуют определенные классы проблем, решать которые с помощью алгоритмов несоизмеримо труднее, чем остальные. Такие задачи можно решать только с помощью очень медленных алгоритмов (или,
Теория сложности занимается не столько изучением трудностей, связанных с решением отдельныхзадач, сколько с бесконечными семействами задач, в каждом из которых любая задача может быть решена с помощью одного и того же алгоритма. Различные задачи такого семейства будут отличаться по «размеру», который выражается некоторым натуральным числом п. (Чуть позднее я объясню более подробно, как фактически этот номер п характеризует размер задачи.) Время, требуемое для решения конкретной задачи из рассматриваемого класса, — а вернее, количество элементарных шагов, — дается некоторым числом N , зависящим от n . Для определенности договоримся, что N — это наибольшее число шагов среди всех задач данного размера n , которое может понадобиться алгоритму для решения. При этом, с ростом n увеличивается также и N . На самом деле, N скорее всего будет расти гораздо быстрее n . Например, N может быть примерно пропорционально n 2 , или n 3 или, скажем, 2 n (которое при больших n значительно превосходит n 2, n 3 n 4, n 5и, вообще, n r для любого фиксированного n ), или даже 2 2 n(которое, в свою очередь, растет еще быстрее).
Конечно, число «шагов» зависит от типа вычислительной машины, на которой применяется алгоритм. Если эта машина принадлежит классу машин Тьюринга, описанному в главе 2, у которых есть только одна лента — что довольно неэффективно — то число N может расти еще быстрее (или, эквивалентно, машина будет работать медленнее), чем в случае с двумя и более лентами. Чтобы избежать этих неопределенностей, вводится широкая классификация всех возможных зависимостей N ( n ), так что, независимо от типа используемой машины Тьюринга, величина темпов роста N будет всегда попадать в одну и ту же категорию. Одна из таких категорий, известная как Р (от названия «полиномиальное время»), включает все темпы роста, которые являются фиксированными кратными n или n 2, n 3, n 4, n 5…. [91] . Это означает, что для любой задачи, попадающей в эту категорию Р (под «задачей» здесь фактически понимается семейство задач, решаемых с помощью единого алгоритма), будет справедлива оценка
91
Понятие «полиномиальный» применяется на самом деле к выражениям более общего вида, скажем, 7 n 4 — З n 3 + 6 n + 15, но это никак не изменит общности наших рассуждений. В любом таком выражении все члены младших степеней n теряют значимость по мере увеличения n (так что в данном примере можно игнорировать все слагаемые, кроме 7 n 4 ).
N <= K x n r
где К и r — константы, не зависящие от n . То есть N не может быть больше, чем число, кратное n в некоторой фиксированной степени.
Простой, пример задачи, безусловно относящейся к Р , — перемножение двух чисел. Чтобы объяснить это, я должен сначала описать, как число n характеризует размер двух чисел, которые надо перемножить. Мы можем принять, что оба числа представлены в двоичной записи и что n / 2 — это просто количество бинарных разрядов в каждом из чисел, так что общее число цифр(то есть битов) у обоих равно n . (Если одно из чисел длиннее другого, то мы можем записать более короткое, начав с дополнительной последовательности нулей, тем самым выровняв их по длине.) Например, если n = 14, мы бы могли рассмотреть произведение
1011010 x 0011011,
которое является, на самом деле, произведением 1011010 х 11011, но
учитывая, что в двоичной системе 0x0=0, 0x1=0, 1x0=0, 1x1=1, 0+0=0, 0+1=1, 1+0=1, 1 + 1 = 10. Число отдельных двоичных перемножений равно (n/2) х (n/2) = n 2/4, а число отдельных двоичных сложений может доходить до n 2/4 — n/2 (включая перенос). Это дает n 2/2 — n/2 отдельных арифметических операций — и мы должны еще учесть несколько дополнительных логических шагов, которые задействованы в операциях переноса. Тогда общее число шагов, игнорируя члены более низкого порядка, равно по существу N = п 2 /2, что, очевидно, является полиномом [92] .
92
В действительности, путем применения некоторых тонких ходов, можно сократить число шагов до величины порядка n log n log ( log n ) для больших n — которая, конечно, все еще принадлежит Р . За подробностями я отсылаю читателя к Кнуту [1981].
В общем случае, мы полагаем «размер» n задачи из некоторого класса равным полному количеству двоичных цифр (или битов), необходимых для задания свободных входных данных в задаче указанного размера. Другими словами, для произвольного размера n задача может иметь до 2 n различных вариантов (ибо для каждой из цифр имеется две возможности — 0 или 1, — а общее количество цифр равно n ), и все они должны одинаково обрабатываться алгоритмом не более, чем за N шагов.
Существует масса примеров (классов) задач, которые не «принадлежат» множеству Р . Например, чтобы вычислить 2 2 rдля заданного натурального r , нам только для записи конечного ответапотребуется около 2 n шагов (где n — число цифр в двоичной записи r ), не говоря даже о самом вычислении. Операция по вычислению
Больший интерес представляют задачи, в которых ответ может быть записан и даже проверен на верность за «полиномиальное» время. Есть очень важная категория (алгоритмически решаемых классов) проблем, обладающих таким свойством. Их называют NP – задачами (классом задач). Точнее, если некоторая задача из класса NP имеет решение, то алгоритм позволит получить это решение, которое затем может быть проверено за «полиномиальное» время. Если же задача не имеет решения, то алгоритм сообщит об этом, но при этом не оговаривается необходимость проверки этого факта за «полиномиальное» или какое бы то ни было время [93] .
93
Если быть точным, классы Р , NP и NP – полный (см. «Теория сложности») определены только для задач типа «да или нет» (скажем, когда заданы a , b , c и спрашивается, выполняется ли для них а х b = c ); но описания, приведенные в тексте, вполне подходят для наших целей.
NP – задачивстречаются во многих областях, причем как в математике, так и в повседневной практике. Я приведу здесь только один простой математический пример: задачу нахождения так называемого « гамильтонова цикла» на графе (довольно устрашающее название для чрезвычайно простой идеи). Под графом подразумевается конечный набор точек, или «вершин», некоторое количество пар которых соединено между собой линиями — «сторонами» графа. (Нас не интересуют сейчас геометрические или линейные свойства, а только то, какие вершины соединяются друг с другом. Поэтому не имеет значения, лежат ли все вершины в одной плоскости — если нас не волнует возможность пересечения двух сторон — или же в трехмерном пространстве.) Гамильтонов цикл — это замкнутый маршрут (петля), состоящий только из сторон графа и проходящий не более одного раза через любую из вершин. Пример графа с изображенным на нем гамильтоновым циклом показан на рис. 4.14. Задача нахождения гамильтонова цикла заключается в том, чтобы определить, существует ли гамильтонов цикл на рассматриваемом графе, и если существует, то явным образом указать его.
Рис. 4.14.Граф с гамильтоновым циклом (изображен зачерненными линиями). Существует только один гамильтонов цикл, как читатель может сам убедиться
Есть разные способы представления графов на языке двоичных чисел. Неважно, какой из этих способов применяется в том или ином случае. Один из методов заключается в том, чтобы пронумеровать вершины 1, 2, 3, 4, 5…, а потом перечислить пары в некотором подходящем фиксированном порядке: