Когда голубей становится больше, чем гнёзд, некоторым птицам приходится ютиться вдвоём. У этого очевидного утверждения — и его обратной стороны — есть глубокие связи со многими областями математики и информатики.
Американцы говорят, что птица в руке стоит двух в кустах, но для компьютерных учёных две птицы в гнезде ещё лучше. А всё потому, что эти сожительствующие птицы являются героями обманчиво простой математической теоремы, называемой принципом голубятни. Её легко сформулировать в одном коротком предложении: если шесть голубей гнездятся в пяти гнёздах, то по крайней мере два из них должны жить в одном гнезде. Вот и всё.
«Принцип голубятни — это теорема, которая вызывает улыбку, — говорит Кристос Пападимитриу, учёный-теоретик из Колумбийского университета. — Это прекрасная тема для разговора».
Но принцип гнёзд подходит не только для птиц. Несмотря на то, что он звучит до боли просто, он стал мощным инструментом для исследователей, занимающихся центральным проектом теоретической информатики: составлением карты скрытых связей между различными задачами.
Принцип гнёзд применим к любой ситуации, когда предметы распределены по категориям, а предметов больше, чем категорий. Например, он подразумевает, что на переполненном футбольном стадионе с 30 000 мест у некоторых зрителей должен быть совпасть их четырёхзначный пароль, или PIN-код, для их банковских карт. В данном случае голуби — это футбольные фанаты, а гнёзда — это 10 000 различных возможных PIN-кодов, от 0000 до 9999. Это меньше, чем общее число людей, поэтому у некоторых из них должны быть одинаковые последовательности цифр.
Это доказательство примечательно не только своей простотой, но и тем, о чём оно умалчивает. Многие математические методы доказательства существования чего-либо являются «конструктивными», то есть они также объясняют, как это что-то можно найти. «Неконструктивные» доказательства, например, основанные на принципе гнёзд, не обладают этим свойством. В примере с футбольным стадионом знание того, что у некоторых людей должны быть одинаковые PIN-коды, не скажет вам, какие именно и у кого. Вы всегда можете пройтись по трибунам, спрашивая каждого человека по очереди. Но есть ли более простой способ?
Вопросы, подобные этому, о наиболее эффективном способе решения задач лежат в основе отрасли информатики, известной как теория сложности вычислений. Теоретики сложности изучают такие вопросы, объединяя проблемы в классы на основе определённых общих свойств. Иногда первым шагом на пути к прорыву становится просто определение нового класса, объединяющего проблемы, которые исследователи ранее не изучали вместе.
Именно так произошло в 1990-х годах, когда Пападимитриу и другие теоретики сложности начали изучать новые классы задач, в которых целью было найти нечто, что должно существовать из-за принципа гнёзд или другого неконструктивного доказательства. Это направление работы привело к важному прогрессу в самых разных областях информатики, от криптографии до алгоритмической теории игр.
К январю 2020 года Пападимитриу думал о принципе гнёзда уже 30 лет. Поэтому он был удивлён, когда игривый разговор с его коллегой привёл их к простому нюансу принципа, о котором они никогда не задумывались: что, если голубей меньше, чем гнёзд? В таком случае любое расположение голубей должно оставлять несколько пустых отверстий. И снова это кажется очевидным. Но имеет ли инверсия принципа гнёзд какие-либо интересные математические последствия?
Может показаться, что этот принцип «пустых гнёзд» — просто изначальный принцип под другим названием. Но это не так, и его тонко различающийся характер сделал его новым и плодотворным инструментом для классификации вычислительных задач.
Чтобы разобраться в принципе пустого гнезда, давайте вернёмся к примеру с банковской картой, перенесённому с футбольного стадиона в концертный зал на 3 000 мест — меньшее число, чем все возможные четырехзначные PIN-коды. Принцип пустого гнёзда гласит, что некоторые возможные PIN-коды вообще не будут представлены. Однако если вы хотите найти один из этих недостающих PIN-кодов, то, похоже, нет лучшего способа, чем просто спросить у каждого человека его PIN-код. Таким образом, принцип пустого гнезда похож на свой более известный аналог.
Разница заключается в сложности проверки решений. Представьте, что кто-то утверждает, что нашёл на футбольном стадионе двух конкретных людей с одинаковыми PIN-кодами. В этом случае, как и в первоначальном сценарии с гнёздами, есть простой способ проверить это утверждение: просто уточнить у двух людей, о которых идёт речь. Но в случае с концертным залом представьте, что кто-то утверждает, что ни у одного человека нет PIN-кода 5926. Это утверждение невозможно проверить, не спросив у всех присутствующих, какой у них PIN-код. Это делает принцип «пустого гнезда» гораздо более сложным для теоретиков сложности.
Через два месяца после того, как Пападимитриу начал думать о принципе пустого гнезда, он затронул эту тему в разговоре с будущим аспирантом. Он хорошо помнит эту беседу, потому что она оказалась его последним личным разговором с кем-либо до ковидных ограничений. В последующие месяцы, сидя дома, он размышлял над тем, как эта проблема влияет на теорию сложности. В конце концов он и его коллеги опубликовали работу о проблемах поиска, которые гарантированно имеют решения благодаря принципу пустого гнезда. Особенно их интересовали задачи, где гнёзд много — то есть где их намного больше, чем голубей. В соответствии с традицией громоздких аббревиатур в теории сложности, они назвали этот класс задач APEPP, что означает «полиномиальный принцип изобилия пустых гнёзд» [abundant polynomial empty-pigeonhole principle].
Одна из задач этого урока была вдохновлена знаменитым доказательством 70-летней давности пионера информатики Клода Шеннона. Шеннон доказал, что большинство вычислительных задач должны быть трудноразрешимыми по своей сути, используя аргумент, основанный на принципе пустого гнезда (хотя он не называл его так). Однако на протяжении десятилетий учёные-компьютерщики пытались и не смогли доказать, что конкретные задачи действительно трудны. Как и в случае с пропажей PIN-кода банковской карты, сложные задачи должны существовать, даже если мы не можем их определить.
Исторически сложилось так, что исследователи не рассматривали процесс поиска трудных задач как проблему поиска, которая сама по себе может быть проанализирована математически. Подход Пападимитриу, который сгруппировал этот процесс с другими проблемами поиска, связанными с принципом пустого гнезда, имел самореферентный привкус, характерный для многих последних работ в теории сложности — он предлагал новый способ рассуждать о сложности доказательства вычислительных трудностей.
«Вы анализируете задачу из теории сложности, используя теорию сложности», — сказал Оливер Кортен, исследователь из Колумбийского университета.
Кортен был перспективным студентом, с которым Пападимитриу обсуждал принцип пустых гнёзд прямо перед пандемией. Он приехал в Колумбийский университет, чтобы работать с Пападимитриу, и в первый же год учёбы в аспирантуре доказал, что поиск сложных вычислительных задач тесно связан со всеми остальными задачами в APEPP. В конкретном математическом смысле любой прогресс в решении этой одной проблемы автоматически приводит к прогрессу в решении множества других, которые давно изучают компьютерщики и математики, например, поиск сетей, в которых отсутствует простая подструктура.
Работа Кортена сразу же привлекла внимание других исследователей. «Я был очень удивлён, когда увидел её, — сказал Рахул Сантханам, теоретик сложности из Оксфордского университета. — Это невероятно захватывающе». С тех пор он и другие исследователи, опираясь на прорыв Кортена, доказали целый шквал новых теорем о связи между сложностью вычислений и случайностью.
«В этом методе есть удивительное богатство, — сказал Пападимитриу. — Благодаря ему мы доходим до сути важных задач в области сложности».
