Теория сложности общения: Как алгоритмы экономят сетевой трафик

Классическая математическая модель выглядит так: есть два участника, по традиции криптографии их называют Алиса и Боб. У Алисы есть строка данных x, у Боба есть строка данных y. Они хотят вычислить значение булевой функции f(x, y). При этом их вычислительные мощности (процессоры и оперативная память) считаются абсолютно безграничными и бесплатными. Единственный ресурс, который мы считаем и оптимизируем — это количество бит, отправленных по каналу связи.

Простейший пример — функция проверки равенства (Equality). Алиса и Боб хотят узнать, совпадают ли их файлы размером 1 Гигабайт побитово. Очевидный детерминированный подход: Алиса просто отправляет свой файл Бобу, он сравнивает и отправляет в ответ 1 бит (да/нет). Коммуникационная сложность такого подхода равна N битам. Математически доказано, что для детерминированного алгоритма невозможно проверить равенство строк, переслав меньше N битов.

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

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