Вопросы на миллион долларов
В 2000 году Математический институт Клэя опубликовал список семи «Проблем тысячелетия» – наиболее важных нерешенных математических задач[153]. В него вошли: гипотеза Ходжа, гипотеза Пуанкаре, гипотеза Римана, квантовая теория Янга – Миллса, проблема существования и гладкости решений уравнений Навье – Стокса, гипотеза Бёрча – Свиннертон-Дайера и проблема равенства классов P и NP. Эти имена и названия мало что говорят подавляющему большинству людей – за исключением тех немногих, кто имеет отношение к специфическим разделам математики, – но главный спонсор института Лэндон Клэй четко обозначил исключительную важность этих гипотез, пообещав выплатить 1 миллион долларов за доказательство или опровержение любой из них. На момент написания книги решена была только проблема с гипотезой Пуанкаре. Гипотеза Пуанкаре – это проблема из области математической топологии. Топологию можно представить как геометрию (математику форм), которая имеет дело с тестом для выпечки. В топологии фактические формы самих объектов неважны, объекты группируются по количеству отверстий, которыми они обладают. Так, для тополога нет разницы между теннисным мячом, мячом для регби или даже фрисби. Если бы все они были сделаны из теста, то теоретически их можно было бы раздавить, растянуть или иным образом переконфигурировать, чтобы они выглядели похожими друг на друга, не прокалывая новых дыр в тесте и не закрывая тех, что есть изначально. При этом эти объекты принципиально отличаются от резинового кольца, камеры шины или обруча баскетбольной корзины – каждый из этих объектов имеет отверстие в середине, как бублик. Фигура в виде восьмерки с двумя отверстиями и крендель с тремя – опять же разные топологические объекты.
В 1904 году французский математик Анри Пуанкаре (тот самый Пуанкаре, который вмешался, чтобы прекратить издевательства над математикой и оправдать капитана Альфреда Дрейфуса в третьей главе), предположил, что самой простой формой в четырехмерном пространстве является четырехмерная проекция сферы. Чтобы объяснить, что для Пуанкаре означало понятие «простой», представьте, будто вы пытаетесь обвязать веревку вокруг некоего объекта. Если вы сможете стянуть эту веревку с объекта так, чтобы при этом она не отрывалась от его поверхности, и чтобы на веревке не завязался узел, то с точки зрения топологии объект тождественен сфере. На языке математики это называется односвязность. Если же трюк у вас не удастся, то вы имеете дело с более сложным топологическим объектом. Представьте, что вы протягиваете струну через центр бублика и делаете петлю. Снять эту струну с бублика, не разомкнув петлю, вы не сможете. Бублик, имеющий одно отверстие, принципиально более сложная фигура, чем футбольный мяч, который отверстий не имеет. Результат в трехмерном пространстве был уже хорошо известен, но Пуанкаре предположил, что та же идея окажется верной и в четырех измерениях. Позднее его предположение обобщили – идея должна быть верной в пространстве с любым количеством измерений. Однако к моменту объявления приза за решение «Проблем тысячелетия» верность гипотезы подтвердили для всех других измерений, и только первоначальная гипотеза Пуанкаре о четырехмерном пространстве оставалась недоказанной.
В 2002 и 2003 годах российский математик-отшельник Григорий Перельман поделился с сообществом топологов тремя сложными для понимания математическими статьями [154]. Эти работы предполагали решение проблемы в четырех измерениях. Несколько групп математиков потратили три года, чтобы удостовериться в верности его доказательств. В 2006 году, в год, когда Перельману исполнилось 40 лет – предельный возраст для получения премии, – он был награжден медалью Филдса, математическим эквивалентом Нобелевской премии. Вручение премии произвело некоторый шум в кругах, далеких от математики, но настоящей сенсацией стал отказ Перельмана от почестей. Он оказался первым человеком, отказавшимся от медали Филдса. В своем заявлении об отказе Перельман сказал: «Меня не интересуют ни деньги, ни слава. Я не хочу, чтобы меня выставляли напоказ, как животное в зоопарке». В 2010 году Математический институт Клэя наконец признал, что Перельман все же заслужил 1 миллион долларов за решение одной из «Проблем тысячелетия», но питерский математик отказался от их денег.
P vs NP
Работа Перельмана, несомненно, чрезвычайно важна в области чистой математики, но применить доказательство гипотезы Пуанкаре на практике шансов немного. То же самое относится и к большинству других «Проблем тысячелетия», которые на момент написания этой книги оставались нерешенными. Однако доказательство или опровержение гипотезы номер семь – известной в математическом сообществе под кратким и несколько загадочным названием P vs NP (а в российском математическом сообществе еще и как проблема перебора) – может иметь широкомасштабные практические последствия в таких разнообразных областях, как интернет-безопасность и биотехнология.
В основе проблемы P vs NP лежит идея, что проверить правильность решения задачи зачастую проще и быстрее, чем собственно решение найти. Этот важнейший из открытых математических вопросов сводится к следующему: если положительный ответ на какой-то вопрос можно довольно быстро проверить при помощи компьютера, верно ли, что ответ на этот вопрос можно довольно быстро найти?
Чтобы провести аналогию, представьте, что вы собираете пазл из однообразного изображения, вроде картинки чистого голубого неба. Перепробовать все возможные комбинации кусочков, чтобы понять, подходят ли они друг другу, – трудная задача; сказать, что она займет много времени – это преуменьшение. Однако, как только пазл закончен, правильность его сборки проверить легко. Более строгие определения эффективности математические выражаются в описании того, насколько быстро работает алгоритм по мере усложнения проблемы – когда к пазлу добавляется больше кусочков. Набор задач, которые можно решить быстро (в так называемом полиномиальном времени), называется классом сложности P. Бóльшая группа задач, которые можно быстро проверить, но не обязательно можно быстро решить, называется классом сложности NP (что расшифровывается как недетерминированное полиномиальное время). Задачи типа P – это подмножество задач типа NP, так как, решив задачу быстро, мы автоматически проверяем найденное решение.
А теперь представьте, что нужно построить алгоритм собирания любого пазла. Если алгоритм входит в группу P, то время, затраченное на его решение, может зависеть от количества элементов пазла, квадрата, куба или даже большей степени этого числа. Например, если алгоритм зависит от квадрата количества элементов, то для сбора пазла из двух элементов может потребоваться 4 (22) секунды, для сбора пазла из 10 элементов – 100 (102) секунд, а для пазла из 100 элементов – 10 000 (1002) секунд. Этот отрезок времени кажется достаточно долгим, но он укладывается в считаные часы. Однако если алгоритм входит в группу NP, то с увеличением количества кусочков время, затрачиваемое на его решение, может вырасти по экспоненте. Если на сбор пазла из 2 элементов понадобятся те же 4 (22) секунды, то на пазл из 10 элементов – уже 1024 (210) секунды, а на пазл из 100 элементов – 1 267 650 600 228 229 401 496 703 205 376 (2100) секунд, что значительно превышает время, прошедшее с момента Большого взрыва. Оба алгоритма требуют больше времени на исполнение с усложнением задачи (ростом количества элементов), но алгоритмы для решения общих проблем группы NP с усложнением задачи быстро становятся непригодными для ее решения. В сущности, литерой «P» можно было бы обозначать проблемы, Решаемые на практике, а литерами «NP» – Не Решаемые на практике.
