Сталкиваясь с по-настоящему масштабными вычислениями, теоретики информатики нередко оказываются в тупике. Классическим примером служит задача о коммивояжёре — поиск кратчайшего пути через множество городов с возвратом в исходную точку. Несмотря на десятилетия поисков, все известные алгоритмы для этой задачи крайне медлительны, и эксперты подозревают, что эффективного решения попросту не существует. Однако строгого математического доказательства этой гипотезы до сих пор нет.
Более полувека специалисты в области теории вычислительной сложности пытаются превратить интуитивное ощущение «эта задача слишком сложна» в неоспоримые теоремы. Всё чаще их внимание смещается на метаматематический вопрос: почему традиционные методы доказательства раз за разом терпят фиаско?
Метаматематика — область, изучающая сами математические доказательства как объекты анализа. Исследователи препарируют аксиомы — фундамент любых логических построений, — меняя их и наблюдая, как это отражается на возможности доказывать те или иные утверждения. В контексте теории сложности это позволяет составить своего рода карту того, что принципиально достижимо в рамках различных систем аксиом.
В недавнем исследовании группа учёных применила нестандартный метод: они перевернули классическую схему, которой математика следовала тысячелетиями. Вместо вывода теорем из аксиом, они возвели саму теорему в ранг аксиомы. Этот метод, известный как реверсивная (обратная) математика, позволил доказать, что многие, казалось бы, разрозненные концепции теории сложности на самом деле логически тождественны.
«Масштаб их успеха впечатляет», — отмечает Марко Кармозино, эксперт из IBM. «В будущем этот труд станет для многих проводником в мир метаматематики».
Принцип Дирихле и поиск фундамента
История этого прорыва началась в 2022 году, когда Лицзе Чен, завершая докторскую диссертацию в Беркли, решил углубиться в изучение метаматематической литературы.
Особый интерес Чена вызвала коммуникационная сложность — раздел, изучающий объем данных, необходимый участникам для совместного решения задачи. Простейший пример — «проблема равенства»: два игрока должны выяснить, совпадают ли их битовые строки, передав минимум информации. Давно доказано, что в худшем случае игрокам придется переслать всю строку целиком. Это и есть «нижняя граница» сложности.
Чен обратил внимание не на саму границу, а на метод её доказательства. Почти все подобные выводы опираются на принцип Дирихле (принцип голубей и ящиков): если распределить N голубей по меньшим M ящикам, хотя бы в одном окажется больше одной птицы. Чен задался вопросом: можно ли пойти в обратном направлении и доказать принцип Дирихле, взяв за основу нижнюю границу проблемы равенства?
Парадоксальная эквивалентность
Объединившись с Цзяту Ли из Университета Цинхуа, Чен выбрал для работы систему аксиом PV1 — достаточно ограниченную, чтобы четко проследить логические связи. В декабре 2022 года они математически подтвердили свою догадку: в рамках PV1 эти две концепции абсолютно взаимозаменяемы.
Позже, при участии Игоря Оливейры из Уорикского университета, ученые обнаружили целую сеть подобных связей. Оказалось, что даже классическая задача о проверке палиндромов на машине Тьюринга логически эквивалентна принципу Дирихле.
«Это звучит невероятно, — признается Чен. — На первый взгляд, принцип подсчета голубей не имеет ничего общего с алгоритмом проверки симметрии строки. Но наша работа доказывает, что нижние границы сложности — это не частные случаи, а проявление фундаментальных законов логики».
Три грани одной истины
Следующие утверждения, несмотря на их внешнюю несхожесть, оказались логически тождественны в рамках исследуемой системы:
- Принцип Дирихле: Невозможно распределить большее число объектов по меньшему числу позиций без дублирования.
- Сложность проверки равенства: Необходимость обмена полным объемом данных для сравнения двух массивов информации.
- Нижняя граница палиндрома: Минимальное время, требуемое машине Тьюринга для распознавания зеркальных строк.
Новый взгляд на старые барьеры
Выявленная сеть эквивалентностей помогла очертить пределы существующих математических систем. Если принцип Дирихле недоказуем внутри PV1, то и связанные с ним задачи сложности также остаются за её рамками. Это объясняет, почему многие десятилетия исследователи не могли продвинуться в доказательствах — они просто использовали недостаточно мощные инструменты.
Хотя Ян Пич из Оксфорда отмечает, что реверсивная математика пока лучше справляется с систематизацией уже известных истин, чем с открытием новых, интерес к метаматематике неуклонно растет. Цзяту Ли уже подготовил фундаментальное 140-страничное руководство для коллег, стремясь популяризировать этот подход.
«Ученые устали от неопределенности, — заключает Кармозино. — Настало время пересмотреть сами основы, на которых строится наше понимание вычислений».
