А что, если голубей меньше, чем гнёзд? Школьная задачка оказалась ключом к сложнейшим проблемам криптографии

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

За этой незамысловатой формулировкой скрывается универсальный математический закон. Он работает в любой ситуации, где объекты распределяются по категориям, а количество объектов превышает число доступных категорий. Теоретик информатики из Колумбийского университета Христос Пападимитриу приводит наглядный пример : на футбольном стадионе с 30 тысячами зрителей обязательно найдутся люди с одинаковыми PIN-кодами банковских карт. Ведь четырехзначный код может принимать только 10 тысяч значений – от 0000 до 9999.

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

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

В январе 2020 года случайный разговор с коллегой натолкнул Пападимитриу на неожиданную мысль: что если перевернуть задачу и рассмотреть ситуацию, где голубей меньше, чем гнезд? В этом случае неизбежно останутся пустые места. Казалось бы, простая перестановка, но "принцип пустой голубятни" открыл новые математические горизонты.

Вернемся к примеру с кодами, но теперь представим концертный зал на 3000 мест – меньше, чем возможных комбинаций PIN-кода. По принципу пустой голубятни какие-то коды гарантированно останутся неиспользованными. Однако проверить утверждение "код 5926 не использует никто из присутствующих" невозможно без опроса всей аудитории. В этом кроется фундаментальное отличие от классического принципа, где достаточно проверить двух конкретных людей, чтобы подтвердить совпадение их кодов.

За время пандемии Пападимитриу с коллегами детально исследовали математические следствия принципа пустой голубятни. Особое внимание уделили ситуациям, где количество "гнезд" значительно превышает число "голубей". Такие задачи объединили в особый класс, названный APEPP (abundant polynomial empty-pigeonhole principle – принцип пустой голубятни с полиномиальным избытком). Название отражает суть: речь идет о задачах, где число возможных вариантов размещения настолько велико, что пустые места гарантированно существуют, причем их количество растет в полиномиальной прогрессии.

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

Оливер Кортен из Колумбийского университета предложил революционное решение. Он впервые рассмотрел сам процесс определения сложных вычислений как отдельную математическую проблему и установил: она неразрывно связана со всеми остальными вопросами класса APEPP. Практическое значение этого открытия трудно переоценить – теперь каждый шаг в понимании природы вычислительной сложности автоматически продвигает науку в самых разных областях, от проектирования компьютерных сетей до оптимизации квантовых вычислений.

"Мы и представить не могли такого поворота событий", – признал профессор Оксфордского университета Рахул Сантанам. Методология Кортена уже позволила доказать несколько важных теорем о природе случайности в алгоритмах. Фактически ученые получили универсальный инструмент для исследования сложных математических структур через анализ отсутствующих элементов – своеобразный "детектор пустоты", открывающий путь к более глубокому пониманию природы вычислений.