Условия присуждения премии за решение проблем тысячелетия размещены на сайте Института Клэя. В частности, предлагаемое решение должно быть опубликовано в рецензируемом журнале и принято математическим сообществом, причем отношение к нему не должно измениться за два года после публикации. После этого специальный консультативный комитет должен рассмотреть вопрос и выдать рекомендацию: присуждать автору премию или нет. Перельман не выполнил первого условия и, судя по всему, никогда уже этого не сделает. С его точки зрения, препринтов на сайте arXiv достаточно. Тем не менее Институт Клэя махнул на это рукой и объявил о начале уставного двухлетнего срока: требовалось посмотреть, не всплывут ли еще какие-нибудь ошибки или вопросы. Срок истек в 2008 г.; теперь нужно было следовать строгой (чтобы, не дай бог, не выдать премию преждевременно) процедуре.
Это правда, что некоторые эксперты не спешили выражать свою уверенность в корректности доказательства Перельмана. Причина понятна: они действительно не были в ней уверены. Не будет преувеличением сказать, что единственным человеком, способным быстро разобраться в доказательстве Перельмана, мог бы быть только второй Перельман. Невозможно читать математическое доказательство с листа, как музыканты читают ноты. Необходимо убедить самого себя в том, что здесь все разумно и имеет смысл. Всякий раз, когда аргументация усложняется, ты понимаешь, что возрастает и вероятность ошибки. То же можно сказать и о ситуации, когда излагаемые идеи становятся слишком простыми: многие перспективные доказательства споткнулись на утверждениях настолько очевидных, что ничего доказывать, казалось бы, вообще не требовалось. До тех пор, пока эксперты не убедились окончательно в том, что доказательство верно в своей основе — а именно в этот момент они признали достижение Перельмана, несмотря на оставшиеся пробелы и ошибки, — разумно было воздержаться от суждений. Вспомните, к примеру, шумиху вокруг холодного синтеза, данные о котором через некоторое время были опровергнуты. Осторожность — верная профессиональная реакция, и в данном случае вполне применимо известное изречение: чрезвычайные заявления требуют чрезвычайных доказательств.
Почему же Перельман отверг Филдсовскую премию и отказался от награды Института Клэя? Это известно лишь ему самому, но вообще-то его никогда не интересовало признание такого рода, и он не раз говорил об этом. Он и раньше отказывался от премий и призов, правда, не таких престижных и крупных. Перельман с самого начала дал понять, что не хочет преждевременной известности. По иронии судьбы, именно это стало одной из причин, по которым специалисты не спешили высказывать свое мнение. Но, по правде говоря, не было ни единого шанса на то, что средства массовой информации не заметят его работу. Много лет математическое сообщество всеми силами старалось заинтересовать этой темой газеты, радио и телевидение, и нет смысла жаловаться на то, что эти усилия увенчались успехом, или ждать, что СМИ пропустят самую громкую математическую сенсацию со времен Великой теоремы Ферма. Но Перельман смотрел на все это иначе и спрятался в раковину. Поступило предложение — и оно остается в силе — использовать премиальные деньги на образовательные или иные цели, если он согласится. До сих пор ответа на это предложение нет.
11. Не могут они все быть легкими. Задача P/NP
В настоящее время математики используют компьютеры для решения самых разных задач, даже великих, и не считают это чем-то из ряда вон выходящим. Компьютеры хороши в числовых расчетах, но математика — это далеко не только «суммирование», так что ввести задачу в компьютер, как правило, очень непросто. Часто самое сложное — это преобразовать ее в такой вид, в каком ее можно решить путем компьютерных расчетов, и даже в этом случае компьютер иногда сопротивляется. Поэтому и в наше время решения многих великих задач находятся без или почти без участия компьютеров. Примерами тому — Великая теорема Ферма и гипотеза Пуанкаре.
В тех случаях, когда компьютеры использовались при решении великих задач (к примеру, теоремы о четырех красках или гипотезы Кеплера), они эффективно выступали в роли прислуги или помощников. Но иногда роли меняются, и математика становится служанкой компьютерной науки. Большая часть работы по первоначальному проектированию компьютеров шла в математическом ключе. Значительную роль в ней сыграла связь между булевой алгеброй — алгебраическим выражением формальной логики — и коммутационными схемами, разработанными, в частности, инженером Клодом Шенноном, создателем теории информации. Сегодня компьютеры и в практическом, и в теоретическом аспекте опираются на широкое использование многих самых разных областей математики.
Одна из задач тысячелетия по версии Института Клэя лежит в пограничной области между математикой и информатикой. В данном случае ситуацию можно рассматривать двояко: то ли информатика находится на службе у математики, то ли наоборот. На самом же деле требуется, да и развивается нечто другое, более сбалансированное, — партнерство. Задача касается компьютерных алгоритмов — математических скелетов, из которых вырастают компьютерные программы. Принципиальное значение здесь имеет концепция эффективности алгоритма: за сколько вычислительных шагов будет получен результат при определенном количестве входных данных. Практически эффективность говорит о том, сколько времени потребуется компьютеру на решение задачи заданного размера.
Слово «алгоритм» восходит к Средним векам, когда Мухаммад ибн-Муса аль-Хорезми написал один из первых трудов по алгебре. Еще раньше Диофант ввел в обращение элементы, которые мы сегодня прочно связываем с алгеброй: символы. У него они, однако, использовались как сокращения, а методы решения уравнений были представлены при помощи конкретных — хотя и типичных — примеров. Там, где мы сегодня написали бы что-нибудь вроде «x + a = y, следовательно, x = y — a», Диофант написал бы: «Положим x + 3 = 10, тогда x = 10 − 3 = 7» — и считал бы, что читатели должны сами сообразить, что эта идея будет работать и для любых других чисел вместо 3 и 10. Он готов был объяснить свой иллюстративный пример с применением символов, но никогда не стал бы оперировать символами как таковыми. Аль-Хорезми подробно разработал эту общую рекомендацию. Он сделал это при помощи слов, а не символов, но общая идея была верной, и именно он считается отцом алгебры. Более того, сам этот термин образован из названия его книги: она называлась «Краткая книга о вычислении посредством восполнения и противопоставления» («Аль-китаб аль-мухтасар фи хисаб аль-джебр ва-ль-мукабала»). Слово «аль-джебр», от которого и пошла алгебра, при этом означало «восполнение» и имело отношение к решению уравнений. А слово «алгоритм» произошло от средневековой латинизированной версии прозвища аль-Хорезми (т. е. «из Хорезма») — Алгорисмус — и означает в настоящее время специализированный математический процесс решения задачи, который при достаточно длительном ожидании гарантирует нахождение ответа на нее.
Традиционно в математике задача считалась решенной, если для нее в принципе можно было записать алгоритм, ведущий к ответу. Слово «алгоритм» использовалось редко: математики предпочитали представлять, скажем, формулу решения — частный случай алгоритма на языке символов. При этом было не слишком важно, может ли эта формула быть применена на практике: она сама по себе являлась решением. Но появление компьютеров изменило эту ситуацию. Формула, слишком сложная для ручных вычислений, вполне могла оказаться применимой, если привлечь на помощь компьютер. Зато ситуации, когда формула оказывалась слишком сложной даже для компьютера, стали вызывать раздражение, а такое тоже иногда случалось: конечно, любой алгоритм можно было попытаться просчитать на компьютере, но иногда расчет шел слишком медленно и не позволял получить ответ. Поэтому внимание ученых сместилось к поиску эффективных алгоритмов. И математики, и компьютерщики были кровно заинтересованы в получении алгоритмов, которые действительно позволяли бы за разумный промежуток времени получить ответ.
Если алгоритм имеется, относительно несложно оценить, сколько времени (измеряемого числом необходимых вычислительных операций) потребуется на решение задачи при определенном количестве входных данных. Это может требовать усилий и технических навыков, но зато вам известно, о каком именно процессе идет речь и, по крайней мере в общих чертах, что он делает. Гораздо сложнее разработать эффективный алгоритм, если тот, с которого вы начали, неэффективен. Еще сложнее решить, насколько плохим или хорошим может быть наилучший с точки зрения эффективности алгоритм для данной задачи, — ведь для этого нужно рассмотреть все возможные варианты, а вам неизвестно, что они собой представляют.
Первые работы по этому вопросу привели к грубому, но удобному разделению алгоритмов на эффективные (в простом, но неточном смысле) и неэффективные. Если продолжительность расчетов с увеличением количества входных данных растет относительно медленно, данный алгоритм эффективен, а задача проста. Если же продолжительность расчетов с увеличением количества входных данных растет очень быстро, то данный алгоритм неэффективен, а задача сложна. Опыт подсказывает, что, хотя встречаются задачи, которые в этом смысле можно назвать простыми, большинство задач к таковым не относятся и являются сложными. В самом деле, если бы все математические задачи были простыми, математики остались бы без работы. Соответствующая задача тысячелетия заключается в том, чтобы строго доказать, что существует по крайней мере одна сложная задача или что, вопреки нашему опыту, все задачи являются простыми. Эта задача известна как задача P/NP, и никто пока не представляет, как ее нужно решать.
В главе 2 мы уже сталкивались с приближенной оценкой эффективности. Алгоритм относится к классу P, если он имеет полиномиальное время работы. Иными словами, если число шагов, которые необходимо сделать для получения ответа, пропорционально количеству входных данных в какой-либо постоянной степени (скажем, в квадрате или кубе). Такие алгоритмы эффективны в самом широком смысле. Если входные данные представлены числом, то их количество — это не само число, а количество знаков в нем. Причина в том, что количество информации, необходимой для представления числа, соответствует месту, которое оно занимает в памяти компьютера, а это место пропорционально количеству цифр. Задача относится к классу P, если существует алгоритм класса P, который ее решает.