Новый ум короля: О компьютерах, мышлении и законах физики

NP- задачи встречаются во многих областях, причем как в математике, так и в повседневной практике. Я приведу здесь только один простой математический пример: задачу нахождения так называемого «гамильтонова цикла» на графе (довольно устрашающее название для чрезвычайно простой идеи). Под графом подразумевается конечный набор точек, или «вершин», некоторое количество пар которых соединено между собой линиями — «сторонами» графа. (Нас не интересуют сейчас геометрические или линейные свойства, а только то, какие вершины соединяются друг с другом. Поэтому не имеет значения, лежат ли все вершины в одной плоскости — если нас не волнует возможность пересечения двух сторон — или же в трехмерном пространстве.) Гамильтонов цикл — это замкнутый маршрут (петля), состоящий только из сторон графа и проходящий не более одного раза через любую из вершин. Пример графа с изображенным на нем гамильтоновым циклом показан на рис. 4.14. Задача нахождения гамильтонова цикла заключается в том, чтобы определить, существует ли гамильтонов цикл на рассматриваемом графе, и если существует, то явным образом указать его.

Рис. 4.14. Граф с гамильтоновым циклом (изображен зачерненными линиями). Существует только один гамильтонов цикл, как читатель может сам убедиться

Есть разные способы представления графов на языке двоичных чисел. Неважно, какой из этих способов применяется в том или ином случае. Один из методов заключается в том, чтобы пронумеровать вершины 1, 2, 3, 4, 5…, а потом перечислить пары в некотором подходящем фиксированном порядке:

(1,2), (1,3), (2,3), (1,4), (2,4), (3,4), (1,5), (2, 5), (3,5), (4, 5), (1,6)….

Затем мы на место каждой пары помещаем «1», если пара соединена стороной графа, и «О» — в противном случае. Тогда двоичная последовательность

10010110110…

будет означать, что вершина 1 соединяется с вершинами 2, 4 и 5; вершина 3 — с вершинами 4 и 5; вершина 4 — с вершиной 5, и т. д. (в соответствии с рис. 4.14). Гамильтонов цикл может быть задан по желанию просто как подмножество этих сторон, которое было бы описано такой же двоичной последовательностью, как и ранее, но со значительно бо́льшим числом нулей. Процедура проверки в этом случае проходит несравненно быстрее, чем процесс непосредственного построения гамильтонова цикла. Все, что нужно выяснить, — это является ли построенный цикл действительно циклом, т. е. принадлежат ли его стороны исходному графу, и что каждая вершина графа используется ровно два раза — по одному разу на концах каждой из входящих в нее двух сторон.

Такую процедуру проверки можно легко завершить за «полиномиальное» время.

На самом деле эта задача относится не только к NP, но к так называемой категории NP- полных задач. Это означает, что любая другая NP- задача может быть сведена к данной за «полиномиальное» время — так что, если бы кому-нибудь удалось отыскать алгоритм для решения задачи нахождения гамильтонова цикла за «полиномиальное» время (т. е. показать, что задача гамильтонова цикла действительно принадлежит Р), то это будет означать, что все NP- задачи будут лежать в Р! Это имело бы очень важные следствия. В широком смысле, задачи из Р считаются «податливыми» (иначе говоря, «решаемыми за приемлемое время») для относительно больших n, на быстром современном компьютере; тогда как задачи из NP, но не лежащие в Р, считаются «неподатливыми» (т. е. решаемыми в принципе, но «нерешаемыми практически») для тех же n— независимо от того, на какое разумно предсказуемое увеличение быстродействия компьютеров рассчитывать в будущем. (Реальное время, которое бы потребовалось для достаточно больших n при решении «неподатливой» задачи, легко превосходит возраст вселенной, что никак не предполагает практическое использование такого подхода!) Любой «умный» алгоритм для решения задачи о нахождении гамильтонова цикла за «полиномиальное» время мог бы быть превращен в алгоритм для решения всех прочих NP- задач, и тоже за «полиномиальное» время!