С нулевым разглашением

В середине марта Норвежская академия наук объявила лауреатов Абелевской премии (одна из самых престижных премий в области математики) за 2021 год. Ими стали Ласло Ловас (László Lovász) и Ави Вигдерсон (Avi Wigderson), работающие в области теоретической информатики. Это, пожалуй, не только признание их личных заслуг, но и теоретической информатики как полноценного раздела математики. И хотя это очень молодая область, она быстро развивается, а новоиспеченные лауреаты премии много чего в ней придумали и доказали. О нескольких примерах их математического творчества IQ.HSE рассказал ассоциированный сотрудник Международной лаборатории теоретической информатики при Факультете компьютерных наук НИУ ВШЭ Александр Шень.

Александр Шень,
ассоциированный сотрудник Международной
лаборатории теоретической информатики
при Факультете компьютерных наук НИУ ВШЭ

Показать не показывая

Одна из стандартных NP-трудных задач — раскраска графа. Нужно покрасить каждую вершину графа в один из трёх цветов, при этом соседние вершины — связанные одним ребром — нельзя красить одинаково. Это сложная задача, для которой не известно быстрых алгоритмов.

Однако предположим, что какому-то заказчику почему-то позарез нужно найти такую раскраску для имеющегося у него графа и он объявляет тендер на выполнение соответствующих работ, хочет заключить контракт. Допустим, вы знаете необходимую раскраску, хотите заключить договор и получить деньги. Как убедить заказчика, что вам известно решение? Можно, конечно, его показать, но тогда зачем заказчику после этого платить деньги? А если не показать, он побоится связываться, и его тоже можно понять. Что же делать?

Если вы встречаетесь с заказчиком вживую, то есть такой выход. Вы вместе рисуете граф на столе, затем он выходит из комнаты, а вы пишете цвета на вершинах и прикрываете их бумажками так, что не видно надписей. Затем он заходит и открывает бумажки на двух любых соседних вершинах. Если там оказывается одинаковый цвет, то вас с позором прогоняют. А если разный, то он снова выходит, вы вновь пишете цвета, переставив их случайным образом, прикрываете бумажками, и всё повторяется. 

Если на самом деле необходимой раскраски вы не знаете и жульничаете, то для графа с 𝐸 рёбрами вероятность разоблачения будет не меньше 1/𝐸 (хоть одно ребро раскрашено с нарушением правил). Можно проверить, что после 10𝐸 повторений вероятность незаметно сжульничать меньше 1/1000, — и на такой риск заказчик готов пойти. С другой стороны, никакого секрета вы не выдаёте: заказчик видит случайную пару разных цветов, и никакой информации на будущее у него не остаётся.

Но что делать в условиях эпидемии COVID-19, когда общаться необходимо только по электронной почте? Ясное дело, что заказчик не может просто спрашивать в письмах про цвета двух соседних вершин графа, потому что вы можете просто назвать два разных цвета, ничего не зная о раскраске графа. В этом случае задача выглядит безнадёжной — и она такой и была, пока к ней не применили теорию сложности вычислений и понятие доказательства с нулевым разглашением информации или, по-английски, Zero-Knowledge Proof, одним из изобретателей которого был Ави Вигдерсон.

Соседи по круглому столу

Другое знаменитое достижение с участием Ави Вигдерсона — это конструкция графов с особыми свойствами, называемых «экспандерами». Пусть есть большой граф, в котором из каждой вершины выходит совсем немного рёбер. Допустим, вершины расположены по кругу и каждая соединена с несколькими близкими вершинами. 

Например, за большим круглым столом сидит много народу, и каждый может докричаться лишь до пары соседей рядом. В такой ситуации информация распространяется плохо: если что-то стало известно одному из сидящих, и он начинает передавать информацию соседям (по рёбрам графа), то до противоположного края стола она дойдёт нескоро. 

Однако бывают и другие графы, в которых по-прежнему мало соседей, но информация распространяется быстро. Их объединяет следующее свойство: если взять какое-то множество вершин и добавить к этим вершинам их соседей, то получится заметно больше вершин, чем в исходном множестве.

Оказывается, что графы с такими свойствами играют важную роль во многих алгоритмах — но построить их совсем не так просто. Прорывом в этой области (в котором важную роль сыграл Ави Вигдерсон) стала конструкция так называемого «зигзаг-произведения»: вполне конкретная и элементарная комбинаторная конструкция, дающая нужные результаты.

В поисках уравнений

С помощью компьютеров легко решать уравнения. Возьмём наугад какое-то алгебраическое уравнение: многочлен с целыми коэффициентами равен нулю.  Можно запустить программу и практически мгновенно найти его корень с тысячами цифр после запятой. Но можно ли сделать наоборот — восстановить уравнение по этому корню? 

Если искомое уравнение не слишком длинное (скажем, записывается в одну строку), то в нём меньше битов, чем мы знаем про корень, так что есть шанс, что информация не утрачена. Но как её извлечь и найти такое уравнение? Ясно, что пробовать все подряд уравнения не вариант — хотя их можно перерешать и сравнить корни с имеющимся, но уравнений так много, что такой грубый перебор окажется бесконечным.

Математически можно сказать так: дано число 𝛼 (корень с большой точностью). Нам надо найти многочлен с целыми коэффициентами, который почти равен нулю в точке 𝛼, то есть найти целочисленную линейную комбинацию чисел 1, 𝛼, 𝛼², ...,, близкую к нулю.

Оказывается, что это вполне реально, и соответствующий алгоритм называется LLL в честь его авторов (Arjen Lenstra, Hendrik Lenstra, Lásló Lovász). Более того — это важный алгоритм и для вполне практических задач, а не только для восстановления уравнения по корню.

Локальная лемма Ловаса

Другой знаменитый результат Ловаса тоже называют LLL (но теперь от Lovász local lemma). Его можно пояснить на таком примере. Пусть в каждую клеточку большого листа клетчатой бумаги нужно вписать число (скажем, трёхзначное). Но есть ограничения: для каждой пары соседних клеток известно, какие пары чисел допустимо вписывать в эти клетки, а какие нет. 

Эти ограничения могут быть свои для каждой пары соседей, но всегда запрещено сравнительно немного (скажем, не более 1% всех пар). Тогда задача гарантированно разрешима — числа можно вписать. Однако это не так просто доказать даже для данного случая. Кстати, попробуйте! 

Впрочем, есть общий результат, из которого следует разрешимость. Его и называют локальной леммой Ловаса и часто используют в различных доказательствах существования в комбинаторике. А недавно придумали и эффективные вероятностные алгоритмы поиска решений.

Вместо заключения

Про биографию — многочисленные другие престижные премии, работу в разных странах — обоих лауреатов можно прочесть в Википедии. Добавим только, что Ласло Ловас и Ави Вигдерсон хорошо знакомы российским учёным: оба бывали в России, а Ловас даже избирался иностранным членом Российской академии наук. Обоих в нашей стране знают, как замечательных математиков и доброжелательных коллег. Вигдерсон и Ловас много сделали для образования в области теоретической информатики. Кроме того Ловас, вернувшись в Венгрию, серьёзно поддержал там науку, став президентом Венгерской академии наук и борясь за её независимость от государственных чиновников.
IQ

Автор текста: Шень Александр, 5 апреля, 2021 г.