Вычислительная сложность и путешествия по решеткам. За что Ави Вигдерсон и Ласло Ловас получили в 2021 году Абелевскую премию
Лауреаты Абелевской премии 2021 года, главной награды математиков, которая вручается по итогам всей научной карьеры, необычно смотрятся в ряду ее прошлых призеров. Специалист в области теории сложности Ави Вигдерсон и комбинаторик Ласло Ловас — пожалуй, самые прикладные исследователи за всю историю премии, одним из результатов работы которых, согласно формулировке комитета премии, стало то, что «дискретная математика и относительно молодая теоретическая информатика оказались в центре современной математики». Серое Фиолетовое постаралось объяснить читателям формулировки наиболее известных достижений Вигдерсона и Ловаса — и рассказать о том, как их можно использовать.
В работах лауреатов 2021 года найдется меньше технически изощренных решений знаменитых проблем и абстрактных теоретических прозрений, чем у большинства других лауреатов премии. Они — авторы множества достаточно конкретных работ, преобразовавших свои области науки путем множества не таких крупных (но иногда очень влиятельных) изменений. Это характерный для комбинаторики и прикладной математики паттерн, где удачное замечание или новый, вполне доступный обычному исследователю и готовый к применению сотнями и тысячами людей метод скорее изменит контекст, чем революционное открытие или теория, требующие для своего понимания многих лет усилий ведущих ученых.
Вычислительные задачи бывают простые и сложные. Простые — те, которые достаточно мощный компьютер сможет решить. Сложные — те, которые ни на каком компьютере решить нельзя: если объем исходных данных будет расти, то время решения быстро превысит время жизни Вселенной, а память — количество элементарных частиц в ней.
В самой простой формализации этого разделения «простыми» окажутся задачи, которые можно решить за время, пропорциональное многочлену от длины входных данных; «сложными» — те, которые нельзя решить быстрее, чем за время, пропорциональное экспоненте от длины входа. Среди них, например, задача определения игрока, обладающего стратегией победы при игре в японский вариант го (в этом варианте запрещено делать ход, возвращающий игру в непосредственно предшествующее состояние).
Однако самое интересное, как обычно, происходит на пограничной территории.
Например, большинство криптографических алгоритмов, используемых в современной электронной коммерции, основано на недоказанной вере в то, что перемножать числа просто, а, напротив, раскладывать их на простые множители существенносложнее.
С 1991 по 2007 год действовал конкурс RSA Factoring Challenge, в рамках которого участникам предлагалось разложить на множители число, про которое известно, что оно является произведением двух простых. В связи с концептуальными успехами вычислительной теории чисел финансовая поддержка конкурса была прекращена, но инженеры бьются над вычислительными задачами до сих пор. Последнее достижение подобного рода датируется февралем 2020-го. Тогда, потратив вычислительные ресурсы, равные 2700 годам работы одного ядра процессора Intel Xeon Gold 6130, команда исследователей из французских и американских научных центров установила, что:
Исходное число записывается 829 двоичными цифрами, до финальной же точки бывшего конкурса, состоящей в разложении числа, записываемого 2048 двоичными цифрами, пройдет, вероятно, еще немало лет.
Именно исследование промежутка между «простотой» и «сложностью» и является одной из основных задач теории сложности алгоритмов, начало которой было положено в 1971 году, когда Стивен Кук в США и одновременно с ним Леонид Левин в СССР задались следующим вопросом: всегда ли можно решить за полиномиальное время на одном процессоре задачу, которую можно решить за полиномиальное время на бесконечно большом числе параллельных процессоров. Сейчас этот вопрос известен как проблема P=NP, названная в 2000 году одной из «проблем тысячелетия».
Вопрос этот отнюдь не праздный, напротив, он носит предельно прикладной характер и касается всевозможных задач перебора: если ответ на вопрос Кука положителен, то для множества таких задач (например, задач поиска оптимального расписания или оптимального маршрута) существует алгоритм, с помощью которого их можно точно решить за разумное время.
Среди «эталонных задач», нахождение полиномиального алгоритма для которых было бы эквивалентно решению проблемы P=NP, есть, например, один из вариантов задачи коммивояжера. Он формулируется следующим образом:
предположим, у нас есть множество городов, связанных дорогами друг с другом. Известна стоимость проезда по каждой из дорог. Требуется узнать, существует ли способ пройти через каждый город ровно по одному разу, потратив не более k единиц стоимости.
Это оптимальный маршрут коммивояжера через 15 крупнейших городов Германии. Он является самым коротким из всех возможных 43 589 145 600 вариантов. Источник
Однако большинство ученых уверено, что ответ на проблему P=NP отрицательный: это соответствует не только научным теориям, но и очевидной вычислительной практике. А раз он отрицательный, но решать переборные задачи необходимо, в игру вступают самые разнообразные ухищрения.
Одно из них — заменить точные решения вероятностными и рассматривать задачи, у которых можно за полиномиальное время найти достаточно надежное, то есть верное с большой вероятностью, решение. Те же ли это задачи, что можно решить бесконечным распараллеливанием, неизвестно (эта проблема называется BPP=NP).
Однако есть достаточно сильные аргументы в пользу того, что любой использующий случайность алгоритм, работающий полиномиальное время, может быть сведен к неслучайному алгоритму, работающему полиномиальное время (проблема BPP=P).
Основная их идея состоит в том, что вместо генератора случайных чисел мы можем использовать некоторый генератор псевдослучайных чисел, который выдаст последовательность значений, достаточную для замены настоящих случайных чисел.
Один из самых сильных результатов подобного рода был получен нашим героем Ави Вигдерсоном вместе с Расселом Импальяццо в 1997 году. Согласно этому результату, если верно, что задача установления по логической формуле того, является ли она когда-либо истинной, в общем случае достаточно сложна (я для простоты изложения не уточняю, в каком именно смысле), то случайность в алгоритмах полиномиальной сложности — необязательный, устранимый элемент.
Для доказательства этого результата была использована теория случайных блужданий на графах-экспандерах (по иронии судьбы, об обоих этих концептах я уже писало в связи с достижениями лауреатов Абелевской премии 2020 года).
Другое важное достижение Вигдерсона связано с криптографией: это результаты о доказательствах с нулевым разглашением, то есть с вопросом о том, как можно сколь угодно надежно подтвердить знание своим партнером какой-то информации, не узнавая эту информацию саму по себе и не давая возможности никакой третьей стороне доказать, что подтверждение действительно произошло.
Самый простой пример доказательства с нулевым разглашением известен как «пещера с нулевым разглашением» и был придуман Жан-Жаком Кискатером и Луи Гиллу в 1990 году.
Рассмотрим пещеру в виде кольца, состоящую из двух ответвлений: правого и левого, разделенных дверью, открыть которую можно, только зная пароль.
Для того чтобы убедиться, что Доказывающий знает пароль, Проверяющий встает около входа в пещеру, а внутрь — в любой из рукавов — заходит Доказывающий. Затем Проверяющий подходит к месту ветвления и кричит Доказывающему название выхода, из которого тому нужно выйти. Если Доказывающий всегда может выйти из выхода, названного Проверяющим, то он может доказать Проверяющему, что, вероятно, знает пароль, ведь Проверяющий не может знать, в какую из веток пошел Доказывающий, а Доказывающий не знает, что ему скажет Проверяющий.
В то же время никакой внешний наблюдатель не сможет понять — не договорились ли Доказывающий с Проверяющим заранее: для наблюдателя всегда остается возможность, что никакого пароля Доказывающий не знает, а просто имеет с собой список инструкций, которым будет следовать Проверяющий.
А несколькими годами ранее, в 1985-м, Ави Вигдерсон, Одед Гольдрайх и Сильвио Микали показали, что доказательства с нулевым разглашением имеют место для всех задач класса NP — решение любой «разумно сложной» задачи можно проверить, не узнавая его!
Сегодня такие протоколы — уже не теоретическая конструкция из компьютерной науки, но передний край практической криптографии: они используются в ориентированных на анонимность криптовалютах, таких как zCash и Monero (в версиях, выпущенных после 2018 года).
Исследования другого абелевского лауреата этого года, Ласло Ловаса, также неразрывно связаны с идеями случайности, криптографии и дискретных объектов. Однако если Ави Вигдерсон в первую очередь специалист в области теоретической информатики, задач, вдохновленных развитием информационных технологий, то основные открытия Ласло Ловаса связаны с теорией графов, восходящей еще к Леонарду Эйлеру и его докладу 1735 года в Санкт-Петербургской академии наук, посвященному невозможности однократного обхода всех мостов в городе Кенигсберге. Впрочем, в отличие от своего учителя Поля Эрдёша, который был одним из самых плодовитых авторов в истории математики и руководствовался только соображениями собственного интереса, Ласло Ловас немало внимания обращает на мотивации, исходящие из потенциально прикладных наук.
Карта 7 мостов Кенигсберга из статьи Леонарда Эйлера Solutio problematis ad geometriam ad geometriam situs pertinentis из журнала Commentarii Academii Scientiarum Imperialis Petropolitanae. Эта статья, отправленная в журнал в 1736-м и опубликованная в 1741 году, стала первой научной публикацией, посвященной теории графов.
Граф — это набор точек-вершин, часть из которых соединены ребрами. Ребра в теории графов понимаются просто как пары вершин. Изображение графа на плоскости или другой поверхности, где ребра нарисованы в качестве отрезков прямых или кривых, — это не сам граф, но его геометрическая реализация.
О важных достижениях Ласло Ловаса в области теории раскрашивания графов и теории случайных графов уже хорошо написал Андрей Райгородский на elementy.ru, я же обращусь к другому его результату — к самому знаменитому вне среды профессиональных математиков достижению ученого, а именно к алгоритму LLL, открытому Ласло Ловасом и братьями Арьеном и Хенриком Ленстра в 1981 году.
Как известно, координаты каждой точки плоскости можно выразить через координаты двух перпендикулярных друг другу координатных векторов x и y длины 1 — говорят, что они образуют ортонормированный базис.
Введение такой системы координат Рене Декартом в начале XVII века впервые сделало геометрические вычисления действительно эффективными и, пожалуй, стало одним из ключевых моментов рождения математики Нового времени. Обобщение метода Декарта на пространства произвольной конечной размерности в XIX веке породило теорию матриц и линейную алгебру — основную вычислительную науку для большинства прикладных дисциплин. А обобщение на бесконечномерные пространства в первой половине XX века стало началом функционального анализа и математической основой квантовой механики. Современные методы обработки звука базируются на теории рядов Фурье, представляющих собой разложения функций по некоторым специальным ортонормированным базисам в бесконечномерных пространствах.
Математиков же интересовал вопрос о том, что делать, если мы хотим найти оптимальный способ достаточно быстро выразить не все вектора нашего пространства, но лишь вектора, принадлежащие некоторой находящейся в нем решетке(то есть множества векторов пространства, которое содержит всевозможные их суммы и целочисленные кратные), через другие вектора этой же решетки.
Синим обозначены точки двумерной решетки, черным — ее исходный базис, красным — почти ортогональный и почти нормированный базис, полученный при помощи применения алгоритма LLL. Источник
В этом случае ортонормированного базиса может не существовать, алгоритм поиска базиса, самого близкого к ортонормированному, оказывается слишком сложным (в размерности выше 4), но можно достаточно быстро найти базис, довольно близкий к оптимальному. Именно эту задачу и решила тройка исследователей в самом начале 1980-х.
Одно из первых своих приложений этот алгоритм нашел в теории чисел. Уже в 1985 году Андрей Одлыжко и Херман те Риле с его помощью опровергли гипотезу Мертенса, поставленную в 1897-м.
Гипотеза состояла в следующем. Каждому натуральному числу можно сопоставить его функцию Мебиуса: она равна нулю, если в разложении числа на простые множители встречаются степени выше 1; равна единице, если число представляет собой произведение четного числа разных простых чисел; и —1, если число раскладывается на нечетное число простых множителей, все из которых различны.
Рассмотрим теперь сумму всех функций Мебиуса для натуральных чисел, не превосходящих некоторого заданного n. Гипотеза Мертенса утверждала, что эта сумма не превысит корня квадратного из n.Если бы гипотеза Мертенса была верна, то из нее бы следовало решение еще одной из «проблем тысячелетия», гипотезы о нулях дзета-функции Римана. Но она оказалась ложной. При этом математикам не понадобилось приводить никакого конкретного контрпримера (он неизвестен до сих пор, известно лишь, что самый маленький контрпример находится где-то в промежутке между 1016 и 106.91*10^39) — они применили алгоритм LLL в некоторых вычислениях с 2000 нулями дзета-функции Римана на тогдашних суперкомпьютерах и с этой помощью смогли дать оценки для верхней грани суммы функций Мебиуса.
Впрочем, для прикладных наук алгоритм LLL оказался не менее полезен. В первую очередь он применяется в задачах криптографии: например, с его помощью была показана нестойкость многих криптосистем.
