Премия Абеля — одна из наиболее престижных наград в области математики, учрежденная Норвежской академией наук в 2002 году. Названная в честь гениального норвежского математика Нильса Хенрика Абеля (1802–1829), она ежегодно присуждается одному или нескольким ученым за выдающийся вклад в развитие дисциплины. О лауреатах премии 2021 года рассказывает докт. физ.-мат. наук, член-корр. РАН, гл. науч. сотр. МИАН, профессор факультета математики Чикагского университета (США) Александр Разборов.
На прошлой неделе были объявлены лауреаты Абелевской премии за 2021 год. Ими стали Ласло Ловас (László Lovász, Математический институт им. Реньи Академии наук Венгрии) и Ави Вигдерсон (Avi Wigderson, Институт перспективных исследований (IAS), Принстон). В соответствии с пресс-релизом [1], премия была присуждена за «основополагающий вклад в теоретическую информатику и дискретную математику и ведущую роль лауреатов в становление этих дисциплин как центральных областей современной математики».
Формулировка Абелевского комитета в данном случае настолько точна и чеканна, что добавить к ней что-либо, по существу, трудно. Поэтому, как и другие пишущие на эту тему авторы (см., например, [2]), я в основном попытаюсь проиллюстрировать содержащиеся в ней (возможно, в слегка завуалированной форме) мысли.
Дискретная математика, как следует уже из названия, занимается изучением свойств конечных, дискретных объектов. Довольно значительная ее часть, традиционно называемая комбинаторикой, мотивирована возникающими в «чистой» математике структурами. Например, фундаментальное для топологии понятие симплициального комплекса с комбинаторной точки зрения не что иное, как замкнутое семейство конечных множеств, соответствующих граням комплекса. Комбинаторная абстракция во многих случаях приводит к замечательным следствиям, и такая «полезная» (т. е., как бы это странно ни звучало, прикладная по отношению к фундаментальной математике) комбинаторика всегда пользовалась заслуженным уважением математического сообщества.
Нас, однако, в этой заметке скорее интересует точка зрения на дискретную математику как на самостоятельную дисциплину, исходящую из того, что изучение конечных структур, таких как, например, графы или множества, в рамках одной связной теории интересно само по себе, вне зависимости от их немедленных приложений. И тогда картина взаимоотношений с «чистой» математикой немедленно становится намного более сложной.
Взгляд, описанный в предыдущем абзаце, в течение долгого времени ассоциировался с тем, что называлось «венгерской математикой», и наиболее активным его сторонником и пропагандистом был, конечно, Пол Эрдёш (Pál Erdős). Ласло Ловас родился в Будапеште (Венгрия) в 1948 году и воспитывался в этой математической культуре. В частности, он познакомился с Эрдёшем в довольно раннем возрасте, и это оказало очень большое влияние на его последующую карьеру и мировоззрение. В некотором отношении Л. Ловаса можно считать прямым наследником П. Эрдёша, продолжившим и в определенном смысле завершившим дело его жизни; об этом речь пойдет ниже.
Становление теоретической информатики
Теоретическая информатика, или, как иногда принято говорить, компьютерные науки, возникла как самостоятельная дисциплина приблизительно в 1970-е годы, когда были заложены основы того, что обычно называют «теорией сложности вычислений». В этой дисциплине, грубо говоря, изучаются вопросы существования или, чаще, несуществования алгоритмов с заданными ограничениями на их эффективность.
Несмотря на свое название, теоретическая информатика — наука строго математическая, и все ее достижения формулируются в виде строгих определений, теорем и лемм, так же как и в других областях математики. Тем не менее, наряду с внутренней логикой развития, теоретическая информатика во многом также руководствуется практическими приложениями, иногда вполне конкретными. Совершенно очевидно, что, как и к любой другой «полуприкладной» дисциплине, отношение к ней «чистых» математиков оставалось в течение долгого времени, мягко говоря, настороженным.
Ави Вигдерсон родился в 1956 году в Хайфе (Израиль), и его студенческие годы пришлись на период становления теоретической информатики, и в частности теории сложности вычислений как отдельной, самостоятельной дисциплины. Во время учебы в аспирантуре Принстона большое влияние на Ави оказал его научный руководитель Дик Липтон (Richard Jay Lipton), один из отцов-основателей теории сложности. Так же как и в случае с Ловасом, теоретическая информатика стала делом его жизни.
Одна из главных заслуг обоих лауреатов (об их конкретных достижениях я поговорю ниже), с моей точки зрения, состоит в том, что процесс взросления и становления обеих дисциплин на протяжении десятилетий во многом определялся их научными работами, а также многосторонней педагогической и популяризаторской деятельностью.
При этом оказалось, что в силу естественных причин — большинство объектов, которыми оперируют компьютеры, дискретны — теоретическая информатика является благодарным потребителем результатов, идей и концепций дискретной математики, многие из которых не были востребованы в «чистой» математике. В свою очередь, потребности теоретической информатики привели к созданию совершенно новых областей дискретной математики, так что это, по моему мнению, один из самых удачных симбиозов в истории науки. Огромнейшая заслуга в этом «переносе идей» из одной области в другую также принадлежит лауреатам премии Абеля этого года.
Изменились в лучшую сторону и отношения с «чистой» математикой и математиками. Например, Ласло Ловас (к слову, иностранный член РАН) был президентом Международного математического союза в течение четырех лет (2007–2010), а позиция Ави Вигдерсона в принстонском IAS относится к Школе математики (the School of Mathematics); в начале описываемого пути то и другое было бы немыслимо. Это происходило более-менее естественным образом, путем накопления в обеих дисциплинах задач, идей и постановок, теснейшим образом связанных со многими областями абстрактной математики и во многих случаях влияющих на ее собственное развитие. И в этом отношении Ласло и Ави относятся к безусловным лидерам.
Переходя к более конкретным вещам, оговорюсь, что даже краткий пересказ наиболее выдающихся достижений обоих лауреатов в заметке такого размера невозможен. Я приведу в качестве примеров по одному общему направлению и по одному конкретному результату; выбор материала полностью субъективен.
От дискретности к непрерывности
Мы отмечали выше, что характерной чертой дискретной математики является ее повышенный интерес к конечным (в отличие от непрерывных) объектам. Ласло Ловас — один из основателей и, пожалуй, главное действующее лицо очень важного проекта, в основу которого заложена прямо противоположная посылка. Оказывается, что очень большие графы и другие комбинаторные объекты можно разумным образом рассматривать как приближения к некоторым естественным непрерывным структурам геометрической или алгебраической природы примерно в том же смысле (аналогия Ловаса), в котором десятичные дроби можно рассматривать как приближения иррациональных чисел. Получается красивая и стройная теория, которая оказывается удивительным образом связанной не только с комбинаторикой, что естественно, но и с совсем разными областями математики и даже физики: алгеброй, анализом, теорией меры, статистической механикой, эргодической теорией и т. д.
Ласло Ловасу принадлежит прекрасно и понятно написанная монография «Большие сети и пределы графов» («Large Networks and Graph Limits»), быстро ставшая классическим текстом в этой области; я рекомендую ее всем заинтересовавшимся читателям.
Теория псевдослучайности
Если называть какую-нибудь одну тему, более всего ассоциирующуюся с именем Ави Вигдерсона, в этой роли, скорее всего, выступит теория псевдослучайности. Начну с исходной мотивации. Многие важнейшие алгоритмы по своей природе вероятностны, то есть используют в своей работе датчики случайных чисел. Однако абсолютная случайность встречается редко, и на практике почти всегда используются так называемые генераторы псевдослучайных чисел, которые выдают за случайные биты, сгенерированные детерминированной процедурой, в надежде, что алгоритм такой подмены «не заметит».
Теория псевдослучайности, грубо говоря, пытается подвести под эту надежду теоретическую базу путем построения генераторов с различной архитектурой и параметрами, для которых удается доказать математически, что они обладают требуемыми свойствами. При этом довольно быстро выясняется, что эти объекты и концепции имеют и другие, совершенно независимые приложения в теории сложности вычислений, а также что соответствующие конструкции связаны с совершенно классическими областями математики, такими как, например, алгебраическая геометрия. Ави Вигдерсон — безусловный и общепризнанный лидер в этой области; ему, в частности, принадлежат как наиболее важные конструкции (генератор Нисана — Вигдерсона), так и их замечательные следствия в теории сложности (теорема Импальяццо — Вигдерсона).
Гипотеза Кнезера
Мой любимый конкретный результат Ласло Ловаса — это его доказательство гипотезы Кнезера. Граф Кнезера — это очень естественный конечный граф, возникающий в алгебраической комбинаторике, и задача состоит в том, чтобы вычислить его хроматическое число — т. е. наименьшее число цветов, в которые его вершины можно покрасить так, что соединенные ребром вершины всегда покрашены в разные цвета.
Предположительно, оптимальную раскраску построить легко; проблема состоит в том, чтобы доказать, что улучшить ее нельзя. Эта проблема, не поддававшаяся никаким комбинаторным усилиям почти 25 лет, была решена в элегантной статье Ловаса 1978 года путем погружения всей сугубо дискретной картинки в многомерную сферу и применения теоремы Борсука — Улама — одного из краеугольных результатов вещественной топологии. Из этого доказательства выросла целая дисциплина, называемая сегодня топологической комбинаторикой, методами которой удалось решить целый ряд других неприступных задач.
Система резолюций
Теория сложности доказательств изучает наличие эффективных доказательств различных естественных утверждений, таких как, например, математические теоремы, утверждения о несуществовании раскраски данного графа в данное число цветов или о том, что данный код не содержит ошибок. Наиболее важной системой доказательств является так называемая система резолюций, в том числе и потому, что основанные на ней алгоритмы имеют широчайшее практическое применение.
Методы исследования системы резолюций были известны довольно давно, но до работы Э. Бен-Сассона (Eli Ben-Sasson) и А. Вигдерсона 2001 года они в лучшем случае носили частный характер. В этой работе был предложен удивительно простой общий метод анализа таких доказательств, основанный на привлечении еще одной меры сложности, называемой шириной. В теории сложности доказательств эта работа стала хрестоматийной и вызвала к жизни целый ряд новых идей и концепций.
(3 оценок, среднее: 4,67 из 5)
Загрузка...
Симплициальные комплексы, мягко говоря, не всегда конечны.:)
Имхо, весьма странно, что ни господин Разборов, ни Вы не вспомнили про понятие нерва покрытия и, особенно, про понятие проекционного спектра, введенные в топологию П.С. Александровым.
Л.К.
Понтрягин “Основы комбинаторной топологии”, параграф 3.
К.
Я-то что?:) Я текстов по истории математики никогда не писал – и конкретными типами симплициальных множеств и спектров, введенных Александровым, никогда не интересовался.
Вы, сударь, типа и книжек по топологии вовсе не писАли, так?
Л.К.
В статье в качестве примера приводятся симплициальные комплексы конечной размерности, а не мощности. Графы тоже вполне бывают бесконечными. Обычно дискретная математика прилагается в геометрии и топологии, обратные примеры связанные с работами Ловаса почти уникальны. Упоминать в статье результаты П.С.Александрова было бы странно ибо это приложение в “обычном” направлении.
В.П., спасибо большое за поддержку, но я имел в виду именно конечные комплексы. По-видимому, следовало более подробно отметить, какую именно топологию я здесь имел в виду, но я точно не знаю как (не “необщую” же писать…)