n, скажем, n2 или n3. Говорят, что эти алгоритмы выполняются за полиномиальное время. Символически их обозначают как класс P. Время выполнения непрактичных алгоритмов растет много быстрее, часто экспоненциально, как 2n или 10n. Алгоритм «просчитать все маршруты» для задачи коммивояжера примерно таков – он выполняется за факториальное время n!, которое растет быстрее любой экспоненты. В промежутке находится серая зона, где время выполнения больше любого полинома, но меньше экспоненты. Иногда такие алгоритмы практичны, иногда нет. В целях настоящей книги мы можем принять очень строгий взгляд и отправить их все в корзину с надписью «непрактичные».
Это не то же самое, что NP.
Эта аббревиатура обозначает куда более тонкое понятие: недетерминированное полиномиальное время. Это время выполнения алгоритма, который может решить, является ли каждое конкретное предложенное решение верным. Вспомним, что число называется простым, если не имеет других делителей, кроме 1 и самого себя, так что числа 2, 3, 5, 7, 11, 13 и т. д. являются простыми. В противном случае число называется составным. Так что 26 – составное число, поскольку равно 2 × 13. Числа 2 и 13 – простые сомножители числа 26. Предположим, что вы хотите найти простой делитель числа, состоящего из 200 десятичных знаков. Вы тратите год на безрезультатный поиск такого числа, а затем в отчаянии обращаетесь за советом к Дельфийскому оракулу. Оракул называет в качестве ответа конкретное большое число. Вы понятия не имеете, откуда оно взялось (в конце концов, оракул обладает волшебным даром предсказания), но вы можете сесть и подсчитать, действительно ли число, названное оракулом, разделит нацело то очень большое число, о котором шла речь. Такой расчет намного, намного проще, чем собственно поиск простого делителя.
Предположим, что всякий раз, когда оракул предлагает ответ, вы можете проверить его при помощи алгоритма с полиномиальным временем выполнения (P). Тогда сама задача относится к классу NP – недетерминированному полиномиальному. Задача оракула намного сложнее вашей, но вы всегда можете решить, верный ли ответ он вам дал.
Очевидно, что проверка предложенного ответа должна быть намного проще его отыскания. Проверить, спрятано ли сокровище в месте, отмеченном крестиком на карте, намного проще, чем выяснить, где этот крестик должен стоять. Или возьмем математический пример: почти все верят, что нахождение простых делителей намного сложнее, чем проверка, является ли делителем данное простое число. В пользу этого свидетельствует, в частности, то серьезное обстоятельство, что быстрые алгоритмы проверки любого предложенного делителя известны, а их поиска – нет. Если P = NP, то для любой задачи, имеющей быстро проверяемый ответ, найти ответ тоже быстро. Это звучит слишком хорошо, чтобы быть правдой, и опыт математиков в решении задач говорит прямо противоположное. Поэтому почти все убеждены, что P ≠ NP.
Однако все попытки доказать это – или опровергнуть – зашли в тупик. Вы можете доказать, что задача принадлежит к классу NP, записав детальный алгоритм и подсчитав время его выполнения, но для доказательства того, что задача не относится к классу P, вам придется рассмотреть все возможные алгоритмы ее решения и показать, что ни один из них не относится к классу P. Как это сделать? Никто не знает.
Из этих попыток проистекает тот любопытный факт, что в одну и ту же категорию попадает огромное число задач-кандидатов. Все эти задачи относятся к NP. Более того, если для какой-то из них можно доказать, что она не принадлежит P, то и все остальные не принадлежат P. Они живут или умирают вместе. Подобные задачи называют NP-полными. Связанную с ними более крупную категорию называют NP-трудными задачами: она состоит из алгоритмов, способных эмулировать решение любой NP-задачи за полиномиальное время. Если выяснится, что данный алгоритм выполняется за полиномиальное время, это автоматически докажет, что то же верно для любой NP-задачи. В 1979 году Майкл Гэри и Дэвид Джонсон доказали, что задача коммивояжера относится к классу NP-трудных{22}. Если P ≠ NP, то любой алгоритм для ее решения потребует время выполнения, превышающее полиномиальное.
Флуд был прав.
Это, впрочем, не повод опускать руки, потому что существует по крайней мере два потенциально возможных пути вперед.
Один, который я разберу прямо сейчас, основан на опыте решения практических задач. Если задача не относится к классу P, то решать ее в случае наихудшего сценария – дело безнадежное. Но наихудшие сценарии часто оказываются очень надуманными и нетипичными для тех примеров, с которыми мы сталкиваемся в реальном мире. Поэтому математики, занимающиеся исследованием операций, начали выяснять, с каким количеством городов они могли бы справиться в реальных задачах. И оказалось, что вариации метода линейного программирования, предложенного Данцигом, Фалкерсоном и Джонсоном, часто позволяют добиться замечательных результатов.
В 1980 году рекорд составлял 318 городов; к 1987 году их уже было 2392. К 1994 году рекорд увеличился до 7397 городов и ответ потребовал около трех лет вычислительного времени сети очень мощных компьютеров. В 2001 году точное решение для 15 112 немецких городов было получено с использованием сети из 110 процессоров. На обычном настольном компьютере этот расчет занял бы более 20 лет. В 2004 году задача коммивояжера была решена для маршрута по 24 978 городам Швеции. В 2005 году группа Concorde TSP Solver решила задачу коммивояжера для маршрута по 33 810 точкам на печатной плате. Рекорды не единственный мотив для таких исследований: методы, использованные в рекордных достижениях, работают необычайно быстро при решении менее масштабных задач. Задачу при числе городов не более сотни обычно можно решить за несколько минут, а не более тысячи – за несколько часов на типовом настольном компьютере.
Другая возможность – удовлетвориться меньшим, то есть решением, которое не слишком далеко от наилучшего, но которое проще найти. В некоторых случаях этого можно добиться, воспользовавшись поразительным открытием, сделанным в 1890 году в настолько новой области математики, что многие ведущие ученые того времени не видели в ней никакой ценности и зачастую не верили результатам, которые постепенно получали их более прогрессивные коллеги. Менее приятным было то, что решаемые ими задачи воспринимались «математикой для математики» и внешне не имели взаимосвязи с чем-то в реальном мире. Их результаты считались абсолютно искусственными, а новые геометрические фигуры, которые они строили, даже окрестили «патологическими». Многие были убеждены, что эти ученые, даже если их результаты верны, не продвигают математику вперед, а лишь воздвигают глупые препятствия, мешающие прогрессу.
Один из методов поиска хороших, но не оптимальных решений задачи коммивояжера родился из таких глупых препятствий. Несколько десятилетий на переломе XIX и XX веков математика находилась в состоянии перехода. Царивший ранее авантюризм почти исчерпал себя, а игнорирование таких фундаментальных вопросов, как «о чем, собственно, идет речь?» и «действительно ли все так очевидно, как всем кажется?», сеяло смятение и растерянность там, где требовались ясность и понимание. Беспокойство по поводу таких продвинутых областей, как дифференциальное и интегральное исчисление, где математики легко и непринужденно разбрасывались бесконечными процессами, постепенно переходило с изотерических вещей на повседневные. Вместо сомнений в интегралах сложных математических функций вроде комплексного логарифма математики стали задаваться вопросом о том, что такое функция. Вместо того чтобы определять непрерывную кривую как кривую, которую можно «свободно нарисовать от руки», они стремились к большей строгости и обнаруживали ее отсутствие. Даже природа такого фундаментального и очевидного объекта, как число, вдруг оказалась весьма туманной. И речь здесь не только о новых конструктах, таких как комплексные числа: речь шла о добрых старых натуральных числах 1, 2, 3. Традиционная математика продолжала идти вперед, опираясь на предположение, что вопросы такого рода со временем непременно разъяснятся и все будет хорошо. Логический статус основ можно было без опаски оставить занудам и педантам. И все же… постепенно формировалось мнение о том, что такой неосмотрительный подход к дисциплине долго не продержится.
Дело по-настоящему осложнилось, когда прежние сумасбродные методы стали давать противоречащие друг другу ответы. Теоремы, издавна считавшиеся правильными, оказывались неверными в особых обстоятельствах. Интеграл, вычисленный двумя способами, давал разные ответы. Последовательности, сходившиеся, как считалось, при всех значениях переменной, иногда расходились. Конечно, все было не настолько плохо, как если бы вдруг обнаружилось, что 2 + 2 иногда равно 5, но все эти странности заставили некоторых ученых задуматься о том, что такое на самом деле 2 и 5, не говоря уже о знаках + и =.
Так что, не прислушиваясь к скептическому большинству – или прислушиваясь не слишком сильно, чтобы изменить свое мнение, – немногочисленные педанты разворошили математическое здание сверху донизу в поисках прочной основы, а затем начали перестраивать его с самого фундамента.
Как при всякой перестройке, получившийся со временем результат отличался от оригинала в некоторых тонких, но тревожных аспектах. Оказалось, что в понятии кривой на плоскости, существовавшем в математике со времен древних греков, имеются скрытые глубины. Традиционные примеры – окружности, эллипсы и параболы Евклида и Эратосфена, квадратриса, которую греки использовали для трисекции углов и поиска квадратуры круга, лемниската философа-неоплатоника Прокла, овалы Джованни Доменико Кассини, циклоиды и их более сложные отпрыски, такие как гипоциклоиды и гиперциклоиды Оле Рёмера, – обладали собственным очарованием и привели в свое время к замечательным успехам. Но, подобно тому как домашние животные создают обманчивую картину жизни в тропических лесах и пустынях, эти кривые были слишком правильными, чтобы представлять дикие сущности, обитающие в математических джунглях. В качестве примеров потенциальной сложности непрерывных кривых они не годились, поскольку были чересчур простыми.