В середине марта Норвежская академия наук объявила лауреатов Абелевской премии (одна из самых престижных премий в области математики) за 2021 год. Ими стали Ласло Ловас (László Lovász) и Ави Вигдерсон (Avi Wigderson), работающие в области теоретической информатики. Это, пожалуй, не только признание их личных заслуг, но и теоретической информатики как полноценного раздела математики. И хотя это очень молодая область, она быстро развивается, а новоиспеченные лауреаты премии много чего в ней придумали и доказали. О нескольких примерах их математического творчества IQ.HSE рассказал ассоциированный сотрудник Международной лаборатории теоретической информатики при Факультете компьютерных наук НИУ ВШЭ Александр Шень.
Показать не показывая
Одна из стандартных NP-трудных задач — раскраска графа. Нужно покрасить каждую вершину графа в один из трёх цветов, при этом соседние вершины — связанные одним ребром — нельзя красить одинаково. Это сложная задача, для которой не известно быстрых алгоритмов.
Однако предположим, что какому-то заказчику почему-то позарез нужно найти такую раскраску для имеющегося у него графа и он объявляет тендер на выполнение соответствующих работ, хочет заключить контракт. Допустим, вы знаете необходимую раскраску, хотите заключить договор и получить деньги. Как убедить заказчика, что вам известно решение? Можно, конечно, его показать, но тогда зачем заказчику после этого платить деньги? А если не показать, он побоится связываться, и его тоже можно понять. Что же делать?
Если вы встречаетесь с заказчиком вживую, то есть такой выход. Вы вместе рисуете граф на столе, затем он выходит из комнаты, а вы пишете цвета на вершинах и прикрываете их бумажками так, что не видно надписей. Затем он заходит и открывает бумажки на двух любых соседних вершинах. Если там оказывается одинаковый цвет, то вас с позором прогоняют. А если разный, то он снова выходит, вы вновь пишете цвета, переставив их случайным образом, прикрываете бумажками, и всё повторяется.
Если на самом деле необходимой раскраски вы не знаете и жульничаете, то для графа с 𝐸 рёбрами вероятность разоблачения будет не меньше 1/𝐸 (хоть одно ребро раскрашено с нарушением правил). Можно проверить, что после 10𝐸 повторений вероятность незаметно сжульничать меньше 1/1000, — и на такой риск заказчик готов пойти. С другой стороны, никакого секрета вы не выдаёте: заказчик видит случайную пару разных цветов, и никакой информации на будущее у него не остаётся.
Но что делать в условиях эпидемии COVID-19, когда общаться необходимо только по электронной почте? Ясное дело, что заказчик не может просто спрашивать в письмах про цвета двух соседних вершин графа, потому что вы можете просто назвать два разных цвета, ничего не зная о раскраске графа. В этом случае задача выглядит безнадёжной — и она такой и была, пока к ней не применили теорию сложности вычислений и понятие доказательства с нулевым разглашением информации или, по-английски, Zero-Knowledge Proof, одним из изобретателей которого был Ави Вигдерсон.
Соседи по круглому столу
Другое знаменитое достижение с участием Ави Вигдерсона — это конструкция графов с особыми свойствами, называемых «экспандерами». Пусть есть большой граф, в котором из каждой вершины выходит совсем немного рёбер. Допустим, вершины расположены по кругу и каждая соединена с несколькими близкими вершинами.
Например, за большим круглым столом сидит много народу, и каждый может докричаться лишь до пары соседей рядом. В такой ситуации информация распространяется плохо: если что-то стало известно одному из сидящих, и он начинает передавать информацию соседям (по рёбрам графа), то до противоположного края стола она дойдёт нескоро.
Однако бывают и другие графы, в которых по-прежнему мало соседей, но информация распространяется быстро. Их объединяет следующее свойство: если взять какое-то множество вершин и добавить к этим вершинам их соседей, то получится заметно больше вершин, чем в исходном множестве.
Оказывается, что графы с такими свойствами играют важную роль во многих алгоритмах — но построить их совсем не так просто. Прорывом в этой области (в котором важную роль сыграл Ави Вигдерсон) стала конструкция так называемого «зигзаг-произведения»: вполне конкретная и элементарная комбинаторная конструкция, дающая нужные результаты.
В поисках уравнений
С помощью компьютеров легко решать уравнения. Возьмём наугад какое-то алгебраическое уравнение: многочлен с целыми коэффициентами равен нулю. Можно запустить программу и практически мгновенно найти его корень с тысячами цифр после запятой. Но можно ли сделать наоборот — восстановить уравнение по этому корню?
Если искомое уравнение не слишком длинное (скажем, записывается в одну строку), то в нём меньше битов, чем мы знаем про корень, так что есть шанс, что информация не утрачена. Но как её извлечь и найти такое уравнение? Ясно, что пробовать все подряд уравнения не вариант — хотя их можно перерешать и сравнить корни с имеющимся, но уравнений так много, что такой грубый перебор окажется бесконечным.
Математически можно сказать так: дано число 𝛼 (корень с большой точностью). Нам надо найти многочлен с целыми коэффициентами, который почти равен нулю в точке 𝛼, то есть найти целочисленную линейную комбинацию чисел 1, 𝛼, 𝛼2, ...,, близкую к нулю.
Оказывается, что это вполне реально, и соответствующий алгоритм называется LLL в честь его авторов (Arjen Lenstra, Hendrik Lenstra, Lásló Lovász). Более того — это важный алгоритм и для вполне практических задач, а не только для восстановления уравнения по корню.
Локальная лемма Ловаса
Другой знаменитый результат Ловаса тоже называют LLL (но теперь от Lovász local lemma). Его можно пояснить на таком примере. Пусть в каждую клеточку большого листа клетчатой бумаги нужно вписать число (скажем, трёхзначное). Но есть ограничения: для каждой пары соседних клеток известно, какие пары чисел допустимо вписывать в эти клетки, а какие нет.
Эти ограничения могут быть свои для каждой пары соседей, но всегда запрещено сравнительно немного (скажем, не более 1% всех пар). Тогда задача гарантированно разрешима — числа можно вписать. Однако это не так просто доказать даже для данного случая. Кстати, попробуйте!
Впрочем, есть общий результат, из которого следует разрешимость. Его и называют локальной леммой Ловаса и часто используют в различных доказательствах существования в комбинаторике. А недавно придумали и эффективные вероятностные алгоритмы поиска решений.
Вместо заключения
Про биографию — многочисленные другие престижные премии, работу в разных странах — обоих лауреатов можно прочесть в Википедии. Добавим только, что Ласло Ловас и Ави Вигдерсон хорошо знакомы российским учёным: оба бывали в России, а Ловас даже избирался иностранным членом Российской академии наук. Обоих в нашей стране знают, как замечательных математиков и доброжелательных коллег. Вигдерсон и Ловас много сделали для образования в области теоретической информатики. Кроме того Ловас, вернувшись в Венгрию, серьёзно поддержал там науку, став президентом Венгерской академии наук и борясь за её независимость от государственных чиновников.
IQ
