Вчера (17 марта) Норвежская академия наук объявила о присуждении абелевской премии за 2021 год. Её получили Ласло Ловас (László Lovász, Будапешт) и Ави Вигдерсон (Avi Wigderson, Принстон) за «за их основополагающий вклад в теоретическую информатику и дискретную математику и ведущую роль в их превращении в центральные области современной математики »
Теоретическая информатика и ее задачи
К теоретической информатике относят и теорию алгоритмов (разработка алгоритмов и изучение их свойств) и теорию сложности вычислений. Иногда сюда же относят криптографию и анализ языков программирования; совсем уж общепринятого описания теоретической информатики, похоже, нет. Во всяком случае, информатика закладывает теоретическую базу для работы современных компьютеров. Так или иначе каждый из нас пользуется ее плодами.
И Ловас и Видгерсон занимались среди прочего вычислительной сложностью. В информатике вычислительные задачи классифицируют по сложности. Среди знаменитых задач тысячелетия — вопрос о совпадении классов сложности P и NP. Никто не знает, совпадают ли эти классы, и тому, кто это выяснит, обещают награду в миллион долларов. Грубо говоря, этот вопрос можно переформулировать так: правда ли, что если ответ к задаче можно проверить довольно быстро, то и решить ее можно довольно быстро. Интуиция подсказывает, что нет: проверить, правильно ли мы сложили паззл, можно довольно быстро; по-видимому, быстрее, чем его сложить. Но строгого доказательства не существует, и история говорит нам, что полагаться на бытовую интуицию в математике нельзя.
Ави Вигдерсон
Ави Вигдерсон серьезно продвинулся в изучении рандомизированных (вероятностных) алгоритмов. Они находят верное решение с высокой вероятностью, и в их работе применяются элементы случайности. На практике встречаются такие задачи, которые не получается решить быстро и наверняка, и тогда рандомизированные алгоритмы могут быть очень полезны.
Когда-то казалось, что со случайностью можно сделать гораздо больше, чем без неё. Но время от времени исследователям удается придумать детерминированные алгоритмы для таких задач, которые раньше решались только вероятностно. Возникает вопрос: бывают ли такие задачи, для решения которых введение случайности существенно? Если для какой-то задачи удалось построить только рандомизированный алгоритм, что это означает: такова природа задачи или нам пока просто не удалось придумать алгоритм?
В 1990-х годах Вигдерсон с коллегами доказали, что в некоторых предположениях всегда можно преобразовать быстрый случайный алгоритм в столь же быстрый детерминированный. Видгерсон включил рандомизированные алгоритмы в теорию сложности и изменил взгляды исследователей на них.
Ласло Ловас
Ласло Ловас был математическим вундеркиндом: три года подряд он завоевывал золотую медаль на международной олимпиаде по математике. Совсем молодым он познакомился с Полом Эрдёшем, который ввел его в мир графов, тогда это было математическое захолустье. Но появление компьютеров дало этой области серьезный толчок к развитию. Теория графов и компьютеры развивались рука об руку, как анализ и физика в XVIII и XIX веках. Ловас создал некоторые фундаментальные алгоритмы для работы с дискретными объектами.
Алгоритм LLL (Ленстры, Ленстры и Ловаса) находит кратчайший почти ортогональный базис на решетке.
На плоскости этот результат не очень впечатляет, но в пространствах высоких размерностей задача оказывается сложной. Это важный алгоритм широкого применения.
Ловас решил много важных задач в теории графов и высказал несколько важных гипотез, которые направляют исследования в этой области. В то время, когда Ави Вигдерсон совершенствовал понятие алгоритмической сложности, Ласло Ловас работал в теории графов, которая помогла уточнить границы между разными классами.
Вигдерсон и Ловас много сделали для того, чтобы установить и углубить связи между двумя областями математики. А теперь их объединяет еще и премия Абеля.
(Как известно, за математические достижения Нобелевскую премию не присуждают, и Абелевская премия в этой области какой-то мере заменяет Нобелевскую.)
Толковая статья на английском языке: https://www.quantamagazine.org/avi-wigderson-and-laszlo-lovasz-win-abel-prize-20210317/