50-летнее путешествие теории сложности к пределам знаний

Насколько сложно доказать, что проблемы труднорешаемы? Теоретики метасложности задаются подобными вопросами уже несколько десятилетий. Ряд недавних результатов начал давать ответы. Комментарий Сохранить статью Прочитать позже

В первую неделю осеннего семестра 2007 года Марко Кармозино с трудом добрался до обязательного курса математики для всех студентов, изучающих компьютерные науки, в Массачусетском университете в Амхерсте. Кармозино, студент второго курса, подумывал бросить колледж, чтобы заняться разработкой видеоигр. И тут профессор задал простой вопрос, который изменил всю его жизнь: откуда вы знаете, что математика действительно работает?

«Это заставило меня сесть и сосредоточиться», — вспоминает Кармозино, ныне работающий в IBM специалистом по теоретической информатике. Он записался на факультативный семинар по работам Курта Гёделя, чьи головокружительные аргументы, основанные на самореференции, впервые выявили пределы математических рассуждений и заложили основу для всех будущих исследований фундаментальных пределов вычислений. Это было очень много для восприятия.

«Я совершенно не понимал, — сказал Кармозино. — Но я знал, что хочу понять».

Сегодня даже опытные исследователи сталкиваются с дефицитом понимания, когда сталкиваются с центральным открытым вопросом теоретической информатики, известным как проблема P и NP. По сути, этот вопрос заключается в том, можно ли решить многие вычислительные задачи, долгое время считавшиеся чрезвычайно сложными, на самом деле легко (с помощью секретного метода, который мы пока не обнаружили), или же, как подозревает большинство исследователей, они действительно сложны. На кону — ни много ни мало природа познаваемого.

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

«Нет никакого плана действий», — сказал Майкл Сипсер, опытный специалист по теории сложности из Массачусетского технологического института, потративший годы на решение этой проблемы в 1980-х годах. «Это как отправиться в дикую местность».

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

«Можно подумать: „Ну, это круто. Может быть, теоретики сложности сошли с ума“», — сказал Рахул Иланго, аспирант Массачусетского технологического института, добившийся некоторых из самых впечатляющих недавних результатов в этой области.

Нажимая кнопку просмотра этого видео, вы соглашаетесь с нашей политикой конфиденциальности.

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

«Стало ясно, что метасложность близка к сути вещей», — сказал Скотт Ааронсон, теоретик сложности из Техасского университета в Остине.

Это история долгого и извилистого пути, который привёл исследователей от проблемы P против NP к метасложности. Это был нелёгкий путь — тропа полна ложных поворотов и препятствий, и она снова и снова замыкается на себе. Однако для исследователей метасложности это путешествие в неизведанные края само по себе является наградой. Как сказал Валентин Кабанец, специалист по теории сложности из Университета Саймона Фрейзера в Канаде, начните задавать, казалось бы, простые вопросы, и «вы понятия не имеете, куда придёте».

Известные Неизвестные

Проблема сравнения P и NP обязана своим невыразительным названием привычке специалистов по теории сложности классифицировать вычислительные задачи по широким «классам сложности» с обозначениями, напоминающими тикеры Nasdaq. Вычислительная задача — это задача, которую в принципе можно решить с помощью алгоритма — точно заданного списка инструкций. Но не все алгоритмы одинаково полезны, и различия между ними указывают на фундаментальные различия между задачами разных классов. Задача специалистов по теории сложности — превратить эти подсказки в строгие теоремы о взаимосвязях между классами сложности.

Эти отношения отражают непреложные истины о вычислениях, которые выходят далеко за рамки какой-либо конкретной технологии. «Это похоже на открытие законов вселенной», — сказал Кабанец.

«P» и «NP» — два самых известных представителя растущего зверинца из сотен классов сложности. Грубо говоря, P — это класс задач, которые можно легко решить, например, упорядочить список по алфавиту. NP — это класс задач с легко проверяемыми решениями, например, головоломки судоку. Поскольку все легко решаемые задачи также легко проверяются, задачи класса P также относятся к классу NP. Но некоторые задачи класса NP кажутся сложными для решения — невозможно сразу интуитивно понять решение судоку, не перебрав множество вариантов. Может быть, эта кажущаяся сложность — всего лишь иллюзия, что существует один простой приём для решения любой легко проверяемой задачи?

Если это так, то P = NP: два класса эквивалентны. Если это так, то должен существовать алгоритм, позволяющий легко решать огромные судоку, оптимизировать глобальные маршруты доставки, взламывать современные шифры и автоматизировать доказательства математических теорем. Если P ≠ NP, то многие вычислительные задачи, разрешимые в принципе, на практике навсегда останутся за пределами нашего понимания.

Исследователи беспокоились об ограничениях формального математического мышления задолго до того, как была впервые сформулирована проблема P и NP, – фактически, задолго до возникновения современной информатики. В 1921 году, борясь с тем же вопросом, который привлек внимание Кармозино почти столетие спустя, математик Давид Гильберт предложил исследовательскую программу, призванную обосновать математику на основе абсолютной достоверности. Он надеялся начать с нескольких простых предположений, называемых аксиомами, и вывести единую математическую теорию, отвечающую трём ключевым критериям.

Первое условие Гильберта, непротиворечивость, было важнейшим требованием отсутствия противоречий в математике: если бы два противоречащих друг другу утверждения можно было доказать, исходя из одних и тех же аксиом, вся теория была бы безнадёжна. Но теория могла бы быть лишена противоречий, но при этом оставаться ограниченной в своих возможностях. Именно это мотивировало второе условие Гильберта, полноту: требование, чтобы все математические утверждения были либо доказуемо истинными, либо доказуемо ложными. Его третий критерий, разрешимость, требовал однозначной механической процедуры определения истинности или ложности любого математического утверждения. Выступая на конференции в 1930 году, Гильберт заявил: «Наш лозунг будет: “Мы должны знать, мы будем знать”».

Всего год спустя Гёдель нанёс первый удар по мечте Гильберта. Он доказал, что саморазрушающее утверждение, такое как «это утверждение недоказуемо», может быть выведено из любого подходящего набора аксиом. Если такое утверждение действительно недоказуемо, теория неполна, но если оно доказуемо, теория противоречива — ещё хуже. В той же работе Гёдель также доказал, что никакая математическая теория никогда не сможет доказать свою собственную непротиворечивость.

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

Затем, в 1936 году, 23-летний аспирант Алан Тьюринг перефразировал условие разрешимости Гильберта на тогда ещё незнакомом языке вычислений и нанёс ему сокрушительный удар. Тьюринг сформулировал математическую модель, ныне известную как машина Тьюринга, которая могла представлять все возможные алгоритмы, и показал, что если бы процедура Гильберта существовала, она бы вписывалась в эту модель. Затем он использовал самореферентные методы, подобные методам Гёделя, для доказательства существования неразрешимых утверждений — или, что то же самое, невычислимых задач, которые не мог решить ни один алгоритм.

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

К 1960-м годам специалисты по информатике разработали быстрые алгоритмы для решения одних задач, в то время как для других единственные известные алгоритмы были невыносимо медленными. Что, если вопрос заключался не только в том, решаемы ли задачи, но и в том, насколько сложно их решить?

«Появляется богатая теория, и мы больше не знаем ответов», — сказал Кармосино.

Расходящиеся пути

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

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

Существуют более сложные алгоритмы поиска гамильтоновых путей, которые показывают лучшие результаты, но время, необходимое алгоритмам для решения задачи, неизменно растёт экспоненциально с размером графа. Графы не обязательно должны быть очень большими, чтобы даже лучшие из открытых исследователями алгоритмов не смогли найти путь «за разумное время», — сказал Рассел Импальяццо, специалист по теории сложности из Калифорнийского университета в Сан-Диего. «И под „разумным временем“ я подразумеваю „до конца Вселенной“».

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

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

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

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

И задача о гамильтоновом пути, и задача о эйлеровом пути относятся к классу сложности NP, включающему все задачи, решения которых можно проверить полиномиальными алгоритмами. Задача о эйлеровом пути также относится к классу P, поскольку её можно решить полиномиальным алгоритмом, но, судя по всему, для задачи о гамильтоновом пути это не так. Почему же эти две задачи о графах, столь внешне похожие, так сильно различаются? В этом суть задачи о сравнении P и NP.

Универсально жесткий

Поначалу классы сложности казались удобными категориями для сортировки задач, которые были похожи, но не связаны напрямую — никто не подозревал, что нахождение гамильтоновых путей как-то связано с другими сложными вычислительными задачами.

Затем, в 1971 году, менее чем через год после переезда в Университет Торонто после отказа в предоставлении постоянной должности в США, теоретик сложности Стивен Кук опубликовал выдающийся результат. Он выявил конкретную задачу класса NP со странной особенностью: если существует полиномиальный алгоритм, способный решить эту задачу, он также может решить любую другую задачу из этого класса. «Универсальная» задача Кука, казалось, была единственным столбцом, поддерживающим класс, казалось бы, сложных задач, отделяя их от простых задач, расположенных ниже. Решите эту одну задачу, и остальная часть NP рухнет.

Кук подозревал, что быстрого алгоритма для его универсальной проблемы не существует, и он заявил об этом в середине статьи, добавив: «Я считаю, что стоит потратить значительные усилия, пытаясь доказать эту гипотезу». «Значительные усилия» оказалось бы преуменьшением.

Примерно в то же время советский студент Леонид Левин доказал аналогичный результат, но при этом выявил несколько различных универсальных задач. Кроме того, американский специалист по теории сложности Ричард Карп доказал, что свойство универсальности, выявленное Куком (и Левиным, хотя Карп и Кук узнали о работе Левина лишь спустя годы), само по себе было практически универсальным. Почти каждая NP-задача без известного полиномиального алгоритма, то есть почти каждая легко проверяемая задача, казавшаяся сложной, обладала тем же свойством, которое стало известно как NP-полнота.

Это означает, что все NP-полные задачи — задача о гамильтоновом пути, судоку и тысячи других — в точном смысле эквивалентны. «У вас есть все эти различные естественные задачи, и все они чудесным образом оказываются одной и той же задачей», — сказал Иланго. «И мы до сих пор не знаем, возможно ли решить эту задачу или нет».

Определение сложности любой NP-полной задачи было бы достаточно для решения вопроса о P и NP. Если P ≠ NP, различие между лёгкими и сложными задачами поддерживается тысячами колонн, каждая из которых одинаково прочна. Если P = NP, всё здание балансирует на грани краха, ожидая, когда упадёт хоть один элемент.

Кук, Левин и Карп объединили, казалось бы, множество разрозненных проблем. Теперь теоретикам сложности оставалось решить лишь одну задачу: равенство P = NP или нет?

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

Предположим, что P = NP. Чтобы доказать это, исследователям потребуется найти быстрый алгоритм для NP-полной задачи, которая может скрываться в каком-то малоизвестном уголке этого огромного ландшафта. Нет никакой гарантии, что они найдут его в ближайшее время: теоретики сложности иногда находили гениальные алгоритмы для, казалось бы, сложных (хотя и не NP-полных) задач лишь после десятилетий работы.

Теперь предположим, что P ≠ NP. Доказать это кажется ещё сложнее. Теоретикам сложности пришлось бы установить, что быстрый алгоритм невозможен, что фактически предвосхищает и сводит на нет все усилия всех будущих исследователей.

Незнание, с чего начать, — часть проблемы. Но нельзя сказать, что исследователи не пытались. Десятилетиями они исследовали проблему с разных сторон и на каждом шагу натыкались на препятствия. «Это одна из самых очевидных истин в теоретической информатике», — сказал Кармозино. «Когда сталкиваешься с таким устойчивым явлением, требуется какое-то объяснение».

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

«Я подумал: „Вот это да, нужно отнестись к этому серьёзно“», — вспоминал Кармозино. Вскоре он настолько увлекся предметом, что его наставник мягко посоветовал ему пересмотреть свои планы на послевузовское образование.

«Он сказал: „Знаешь, если хочешь продолжать этим заниматься, если хочешь продолжать изучать теоретическую информатику и теорию сложности, то можешь: это называется аспирантура“», — сказал Кармозино. Получив степень магистра, он переехал в Сан-Диего в 2012 году, чтобы работать над докторской диссертацией под руководством Импальяццо.

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

Этот «естественный барьер доказательств» — лишь одно из многих известных препятствий на пути решения открытых задач в теории сложности. Каждое из них действует как препятствие, предупреждая, что кажущийся многообещающим путь на самом деле тупиковый. В совокупности эти препятствия указывают на то, что любое доказательство, решающее проблему P- и NP-классов, должно радикально отличаться от всего, что использовалось в прошлом; именно поэтому большинство исследователей считают, что решение ещё далёко от реальности. Но, по крайней мере, барьеры подсказывают им, куда не следует искать.

«Теория сложности одновременно проклята и благословлена множеством препятствий», — сказал Иланго.

К тому времени, как Кармозино столкнулся с барьером естественных доказательств, ему было почти 20 лет. Но он подозревал, что он может преподать исследователям ещё больше уроков. Это чувство однажды подтвердилось, когда он и трое его коллег доказали удивительный результат, изучив барьер естественных доказательств с точки зрения метасложности. Их доказательство стало одним из немногих важных результатов, которые пробудили новый интерес к метасложности, что привело к бурному прогрессу в последние несколько лет.

Но чтобы проследить путь от барьера естественных доказательств к метасложности, нам придётся вернуться к тому, с чего мы остановились у исследователей в 1970-х годах, когда они впервые начали решать проблему P и NP. Что же делало так сложно доказывать сложные задачи?

Извилистый путь

Сначала исследователи пытались доказать, что P ≠ NP, то есть доказать, что некоторые задачи класса NP неразрешимы никаким возможным полиномиальным алгоритмом, используя вариации методов, которые Тьюринг использовал для доказательства неразрешимости некоторых задач никаким алгоритмом. Но они быстро обнаружили доказательство неработоспособности этих методов — первое серьёзное препятствие на пути решения вопроса о соотношении P и NP. Поэтому они начали искать другой подход и вскоре нашли его в работе современника Тьюринга, Клода Шеннона.

Шеннон, выросший в небольшом городке на севере Мичигана, казался маловероятной фигурой для наступления информационной эпохи. Тем не менее, он был примером междисциплинарного характера новой дисциплины компьютерных наук, одинаково хорошо разбираясь в электротехнике и математической логике. В своей магистерской диссертации Шеннон показал, как схемы, состоящие из электромеханических переключателей, могут представлять логические выражения с булевыми переменными — величинами, которые могут принимать только два значения (например, «истина» или «ложь», или 1 и 0).

В этих выражениях булевы переменные связаны между собой логическими вентилями И, ИЛИ и НЕ. Например, элементарное выражение A AND B истинно, когда оба значения A и B истинны, и ложно в противном случае; A OR B, с другой стороны, истинно, если хотя бы одна из двух переменных истинна. Вентиль НЕ ещё проще: он инвертирует значение одной переменной. Имея достаточное количество этих базовых элементов, можно выполнить любое вычисление.

«Когда вы смотрите на свой компьютер, что он делает в конце дня? Он управляет цепью», — сказал Иланго.

Работа Шеннона предложила теоретикам новый подход к оценке сложности вычислительных задач, называемый «сложностью схем», хотя рассматриваемые схемы — всего лишь математические абстракции. Некоторое время исследователи полагали, что этот подход может помочь разрешить противоречие между P и NP, но в конечном итоге их путь уперся в барьер естественных доказательств.

Концепция сложности схем требует переосмысления самых базовых концепций модели вычислений Тьюринга. Здесь, вместо вычислительных задач и решающих их алгоритмов, исследователи рассматривают булевы функции и схемы, которые их вычисляют. Булева функция принимает булевы переменные — «истина» и «ложь», «1» и «0» — и выдаёт «истина» или «ложь», «1» или «0». И, подобно алгоритму, схема описывает процедуру получения выходных данных при любых входных данных.

«Насколько я понимаю, люди начали изучать сложность схем, потому что решили, что машины Тьюринга слишком сложны», — сказал Райан Уильямс, специалист по теории сложности из Массачусетского технологического института. «Мы можем изучать схемы поэлементно».

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

Но во многих случаях можно рассматривать более сложные версии той же функции, увеличивая число входных переменных, подобно тому, как можно усложнить задачу о гамильтоновом пути, рассматривая более крупные графы. Затем исследователи задаются тем же вопросом, который они задают при изучении времени выполнения алгоритмов: растёт ли минимальное количество вентилей, необходимое для вычисления булевой функции, полиномиально или экспоненциально с увеличением числа входных переменных? Исследователи называют эти две категории функций «легко вычисляемыми» и «сложно вычисляемыми» соответственно.

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

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

«Маленьких трасс просто не хватает на всех», — сказал Ааронсон.

Итак, теоретики сложности оказались в любопытной ситуации. Если почти каждая таблица истинности имеет высокую сложность схемы, то почти каждая булева функция должна быть трудновычислимой. Исследователям оставалось лишь найти одну такую функцию, которая также была бы известна как принадлежащая классу NP. Насколько это может быть сложно?

КриптоБратья

Поначалу прогресс был быстрым. В 1981 году Сипсер и двое его коллег доказали, что вычисление определённой булевой функции определённо затруднено, если использовать схемы с определёнными ограничениями на расположение вентилей.

«Мы думали, что сможем доказать что-то в этих ограниченных моделях, а затем развить полученные знания, чтобы работать со все меньшими и меньшими ограничениями», — сказал Сипсер.

В 1985 году Разборов сделал следующий большой шаг. Он только что поступил в аспирантуру в Москве и присоединился к проекту случайно, работая над задачей в другом разделе математики, где, как оказалось, решение задачи сравнения P и NP было необходимым условием.

«Мне просто повезло, что я не знал, насколько сложна эта проблема», — сказал Разборов. «Иначе, возможно, я бы даже не начал».

Разборов проанализировал схемы, содержащие только элементы И и ИЛИ, и доказал, что вычислить определённую функцию с помощью таких схем сложно, независимо от расположения элементов. Более того, было известно, что эта функция является NP-полной. Всё, что нужно было сделать исследователям для разрешения противоречий между P и NP, — это распространить методы Разборова на схемы с элементами НЕ.

«Было какое-то всеобщее ощущение, что ещё один шаг, ещё один удар, и мы добьёмся своего», — сказал Разборов. Но этого не произошло. Сам Разборов доказал, что его метод не сработает, если к нему добавить НЕ-ворота, и никто не мог найти другого пути. С годами он начал задаваться вопросом, почему след затерялся.

В США Рудич размышлял над тем же вопросом. Он и Импальяццо были однокурсниками и вместе учились в аспирантуре. Их дружба зародилась на почве общего интереса к самореферентным доказательствам Гёделя и Тьюринга и их влиянию на основы математики и информатики.

«Наша шутка заключалась в том, что мы собирались сделать кнопку с надписью «Самостоятельная ссылка», — сказал Импальяццо.

Будучи аспирантами, Рудич и Импальяццо работали над теоретико-сложностными основами криптографии — предметом, который, пожалуй, является лучшей практической мотивацией для попытки доказать равенство P ≠ NP. Криптографы скрывают секретные сообщения, маскируя их «псевдослучайностью» — сообщение, зашифрованное таким образом, будет выглядеть для любого перехватчика как случайный набор цифр, но получатель всё равно сможет его расшифровать. Но как можно быть уверенным, что потенциальному перехватчику будет слишком сложно взломать код?

Вот тут-то и вступает в дело теория сложности. Все наиболее распространённые сегодня методы шифрования основаны на, казалось бы, сложных NP-задачах — для расшифровки сообщения злоумышленнику потребуется пока ещё не открытый быстрый алгоритм решения этой задачи. Чтобы убедиться в том, что эти методы действительно надёжны, нужно доказать, что P ≠ NP. Без доказательства, сказал Сипсер, остаётся только «надеться, что тот, от кого вы пытаетесь сохранить секрет, не лучший математик, чем вы».

Криптография, хотя и увлекательна сама по себе, казалась весьма далёкой от самореферентных аргументов, которые изначально привлекли Рудича и Импальяццо в эту область. Но пока Рудич пытался понять, почему подход, основанный на сложности схем, зашёл в тупик, он начал понимать, что эти две темы не так уж и далеки друг от друга. Стратегия, принятая исследователями в попытках доказать, что P ≠ NP, имела саморазрушительный характер, напоминая знаменитое утверждение Гёделя «это утверждение недоказуемо», — и криптография могла помочь объяснить, почему. В России Разборов обнаружил похожую связь примерно в то же время. Это были зачатки естественного барьера доказательств.

Проблема, лежащая в основе барьера естественных доказательств, заключается в том, что задача различения функций высокой сложности от функций низкой сложности аналогична задаче различения истинной случайности от псевдослучайности, используемой для шифрования сообщений. Мы хотели бы показать, что функции высокой сложности категорически отличаются от функций низкой сложности, чтобы доказать, что P ≠ NP. Но мы также хотели бы, чтобы псевдослучайность была неотличима от случайности, чтобы быть уверенными в безопасности криптографии. Возможно, мы не можем совмещать и то, и другое.

Жестокая шутка

В 1994 году Разборов и Рудич поняли, что пришли к схожим выводам, и начали работать вместе, чтобы объединить свои результаты. Сначала они заметили, что все предыдущие попытки доказать P ≠ NP с помощью схемной сложности основывались на одной и той же общей стратегии: выявить особое свойство NP-полной булевой функции, а затем доказать, что никакая легко вычисляемая функция не может обладать этим свойством. Это означало бы, что выбранная NP-полная функция действительно трудно вычислима, и таким образом доказывалось бы, что P ≠ NP.

Сипсер, Разборов и другие успешно использовали эту же стратегию для доказательства своих более ограниченных результатов, и во всех случаях особое свойство, выявленное исследователями, было общим для большинства булевых функций. Разборов и Рудич ввели термин «естественное доказательство» для обозначения случая, когда это свойство было широко распространено просто потому, что не было известной альтернативы. Если бы «неестественные» доказательства были возможны, они должны были бы быть крайне контринтуитивными и заслуживающими этого названия.

Затем Разборов и Рудич доказали свой главный результат: естественное доказательство равенства P ≠ NP потребовало бы очень глубокого понимания различий между легковычислимыми и трудновычислимыми функциями, и это знание также могло бы стать основой для быстрого алгоритма обнаружения легковычислимых функций, даже если они внешне сложны. Если бы специалистам по теории сложности удалось получить естественное доказательство равенства P ≠ NP, они бы открыли практически безошибочный способ, взглянув на произвольную таблицу истинности, определить, имеет ли соответствующая функция высокую или низкую схемную сложность — гораздо более сильный и общий результат, чем они намеревались доказать.

«Вы почти ничего не можете поделать, но получите больше, чем рассчитывали», — сказал Кармосино.

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

Чтобы понять эту связь, представьте, что вы смотрите на выходной столбец в таблице истинности булевой функции со многими входными переменными и заменяете каждое «истина» на 1, а каждое «ложь» на 0:

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

Итак, результат Разборова и Рудича показал, что любое естественное доказательство равенства P ≠ NP также приведёт к быстрому алгоритму, способному отличать псевдослучайные строки, содержащие скрытые сообщения, от действительно случайных. Безопасная криптография была бы невозможна — полная противоположность тому, что исследователи надеялись установить, доказав равенство P ≠ NP.

С другой стороны, если безопасная криптография возможна, то естественные доказательства не являются жизнеспособной стратегией для доказательства того, что P ≠ NP — необходимое условие для безопасной криптографии. Вот вкратце суть барьера естественных доказательств. Казалось, что теоретики сложности стали жертвой жестокой шутки.

«Если вы верите в твёрдость, то вы должны верить и в то, что твёрдость трудно доказать», — сказал Кабанец.

В Метавселенную

Эта связь между следствиями гипотезы P ≠ NP и сложностью её доказательства была интригующей, но её было сложно определить. Во-первых, барьер естественных доказательств блокировал лишь один подход к доказательству P ≠ NP. Во-вторых, он связывал сложность доказательства P ≠ NP не с самим P ≠ NP, а с существованием надёжной криптографии — тесно связанной, но не совсем эквивалентной проблемой. Чтобы по-настоящему понять эту связь, исследователям необходимо было бы освоиться с метасложностью.

«Есть такое интуитивное представление: „О, поскольку P ≠ NP, то трудно доказать, что P ≠ NP“», — сказал Уильямс. «Но чтобы хотя бы понять это интуитивное представление, нужно начать рассматривать задачу доказательства чего-то вроде P ≠ NP как вычислительную задачу».

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

«Мне хотелось заниматься чем-то более академическим», — вспоминал Кабанец. «И мне также было любопытно посмотреть мир». Он переехал в Канаду, чтобы учиться в аспирантуре, и именно там узнал о барьере естественных доказательств. Как и Кармозино, Кабанец был поражён результатом. «Эта связь казалась очень глубокой», — сказал он.

В 2000 году, к концу обучения в аспирантуре, он обнаружил, что барьер естественных доказательств постоянно всплывает в его разговорах с Цзинь-И Каем, специалистом по теории сложности, который в то время находился в Торонто в академическом отпуске. Они начали воспринимать этот барьер не как препятствие, а как приглашение — возможность точно выяснить, насколько сложно доказать сложность задач. Статья, в которой они изложили этот новый подход, стала одной из самых влиятельных ранних работ в зарождающейся области метасложности.

В статье Кабанец и Цай была выявлена вычислительная проблема, неявно присутствующая в формулировке Разборова и Рудича барьера естественного доказательства: по таблице истинности булевой функции определить, имеет ли она высокую или низкую схемную сложность. Они назвали это задачей минимального размера схемы (MCSP).

MCSP — это квинтэссенция проблемы метасложности: вычислительная задача, предметом которой является не теория графов или какая-либо другая внешняя тема, а сама теория сложности. По сути, это своего рода количественная версия вопроса, который побудил теоретиков сложности в 1980-х годах заняться вопросом о P и NP, используя подход схемной сложности: какие булевы функции вычислить сложно, а какие легко?

«Если бы мы разработали алгоритм MCSP, это было бы своего рода способом автоматизировать нашу работу в области теории сложности», — сказал Импальяццо. «Это должно как минимум дать нам ценное представление о том, как лучше выполнять нашу работу».

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

Для задач класса NP на вопрос «насколько это сложно?» обычно ответить достаточно легко, но MCSP, похоже, оказался странным исключением. «У нас очень мало „плавающих“ задач, которые не были бы связаны с этим островком NP-полных задач, хотя они кажутся сложными», — сказал Кабанец.

Кабанец знал, что они с Каем были не первыми, кто рассматривал задачу, названную ими MCSP. Советские математики изучали очень похожую задачу, начиная с 1950-х годов, пытаясь понять внутреннюю сложность различных вычислительных задач. Леонид Левин бился над ней, разрабатывая то, что впоследствии стало теорией NP-полноты в конце 1960-х, но не смог доказать её NP-полноту и опубликовал свою основополагающую статью без неё.

После этого проблема не привлекала особого внимания в течение 30 лет, пока Кабанец и Цай не заметили её связи с естественным барьером доказательств. Кабанец не рассчитывал решить этот вопрос сам — вместо этого он хотел разобраться, почему было так сложно доказать, что эта, казалось бы, сложная задача о вычислительной сложности действительно сложна.

«В каком-то смысле это мета-мета-сложность», — сказал Рахул Сантанам, теоретик сложности из Оксфордского университета.

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

Также возможно, что MCSP не является NP-полной задачей, но это тоже кажется маловероятным — некоторые более простые варианты задачи уже известны как NP-полные.

«У нас просто нет подходящего места, чтобы напрямую связать это со всеми остальными проблемами, которые мы изучаем», — сказал Импальяццо.

Кабанец пролил свет на странное поведение MCSP, но не знал, как добиться дальнейшего прогресса. Исследования метасложности замедлились до минимума. Они вновь расцвели 16 лет спустя, когда исследователи обнаружили удивительную связь с другим фундаментальным вопросом: насколько сложно решать задачи, если большую часть времени вас волнует только правильный ответ?

Война миров

Для повседневных задач часто достаточно решений, которые работают в большинстве случаев. Например, мы планируем поездки на работу с учётом типичных дорожных условий, а не худших вариантов развития событий.

Большинству теоретиков сложности удовлетворить сложнее: они готовы объявить задачу лёгкой, только если смогут найти быстрый алгоритм, дающий правильный ответ для всех возможных входных данных. Этот стандартный подход классифицирует задачи по тому, что исследователи называют сложностью «в худшем случае». Но существует также теория сложности «в среднем случае», согласно которой задачи считаются лёгкими, если существует быстрый алгоритм, дающий правильный ответ для большинства входных данных.

Это различие важно для криптографов. Представьте себе вычислительную задачу, которую легко решить практически для любых входных данных, за исключением нескольких трудноразрешимых случаев, когда лучший алгоритм не справляется. Теория сложности в худшем случае считает эту задачу сложной, но для криптографии она бесполезна: если только некоторые из ваших сообщений трудно расшифровать, какой в этом смысл?

Фактически именно Левин инициировал тщательное исследование сложности в среднем случае, спустя десятилетие после своей пионерской работы о NP-полноте. В последующие годы он вступил в конфликт с советскими властями: он был дерзким смутьяном и время от времени подрывал патриотическую деятельность своей молодёжной группы коммунистической партии. В 1972 году ему отказали в докторской степени по явно политическим мотивам.

«Чтобы добиться успеха в Советском Союзе, будучи молодым исследователем, нельзя было иметь слишком большое мнение, и трудно представить себе Леонида, который не был бы таковым», — сказал Импальяццо.

Левин эмигрировал в США в 1978 году и в середине 1980-х годов обратил внимание на сложность вычислений в среднем случае. Он начал работать с другими учёными, включая Импальяццо, который в то время был аспирантом, над дальнейшим развитием этой теории. Но даже по мере продвижения вперёд Импальяццо обнаружил, что исследователи часто перебивают друг друга. Он хотел, чтобы все были на одной волне, и этому способствовала известная лаконичность статей Левина — та, которая положила начало изучению сложности вычислений в среднем случае, была объёмом менее двух страниц.

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

Статья, опубликованная в 1995 году, мгновенно стала классикой. Импальяццо придумал причудливые названия для пяти миров, различающихся по степени вычислительной сложности и криптографическим возможностям. Мы живём в одном из этих миров, но не знаем, в каком именно.

С тех пор, как появилась статья Импальяццо, исследователи мечтали исключить части его миниатюрной мультивселенной, сузив пространство возможностей, доказав, что некоторые миры всё-таки невозможны. Два мира представляют собой особенно заманчивые цели: те, где криптография невозможна, несмотря на то, что P ≠ NP.

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

Эти два мира оказываются тесно связаны с проблемами метасложности — в частности, судьба Heuristica связана с давним вопросом о том, является ли MCSP NP-полной. Вопрос, который так давно увлекал Кабанец и ставил в тупик Левина, — не простое любопытство: на кону целый мир.

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

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

Исследователям пришлось искать другой подход, и теперь они полагают, что MCSP может быть именно той проблемой, которая им нужна. Но это стало ясно только через десять лет. Первые признаки этой связи появились благодаря постоянному интересу Марко Кармозино к естественным барьерам.

Кармозино впервые познакомился с исследованиями метасложности, будучи аспирантом, благодаря работе Кабанеца и четырёх других исследователей, опубликованной в 2013 году. В ней был развит подход к проблеме естественного барьера доказательств, впервые предложенный Кабанецем более десяти лет назад. Это лишь укрепило его убежденность в том, что классическая работа Разборова и Рудича ещё многому может научить.

«В то время я был просто одержим этой газетой, — сказал Кармозино. — Ничего не изменилось».

Одержимость наконец принесла плоды во время посещения семестрового семинара в Калифорнийском университете в Беркли, где он провёл большую часть времени, общаясь с Импальяццо, Кабанец и Антониной Колоколовой, специалистом по теории сложности из Мемориального университета Ньюфаундленда, которая сотрудничала с Кабанец над статьёй 2013 года. Кармозино уже работал с этими тремя, и это успешное сотрудничество придало ему уверенности, чтобы засыпать их вопросами по теме, которая его больше всего увлекала.

«Он по-хорошему доставал людей», — вспоминал Кабанец.

Поначалу у Кармозино появились новые идеи для доказательства NP-полноты для версии MCSP, появившейся в статье Разборова и Рудича о барьере естественных доказательств. Но эти идеи не сработали. Вместо этого импровизированное замечание Импальяццо заставило четырёх исследователей осознать, что барьер естественных доказательств может привести к созданию более мощных алгоритмов, чем кто-либо предполагал — на барьере была выгравирована секретная карта.

В статье 2016 года четверо исследователей доказали, что определённый тип алгоритма MCSP для среднего случая может быть использован для построения алгоритма для наихудшего случая, выявляющего закономерности, скрытые в случайных на вид строках цифр — задачи, которую специалисты по информатике называют «обучением». Это поразительный результат, поскольку обучение интуитивно кажется сложнее, чем задача бинарной классификации — высокой или низкой сложности, — выполняемая алгоритмом MCSP. И, что удивительно, он связал наихудшую сложность одной задачи со средней сложностью другой.

«Было неочевидно, что такая связь вообще существует», — сказал Импальяццо.

Быстрый алгоритм для MCSP является чисто гипотетическим для общих булевых схем: он не может существовать, если MCSP не окажется простой вычислительной задачей, несмотря на все доказательства обратного, и это означает, что алгоритм обучения, подразумеваемый в статье четырех исследователей, является столь же гипотетическим.

Но для некоторых более простых версий MCSP — для различения таблиц истинности высокой сложности от таблиц низкой сложности при наличии определённых ограничений на схемы — быстрые алгоритмы известны уже много лет. В работе Кармозино, Импальяццо, Кабанец и Колоколовой показано, что эти алгоритмы можно преобразовать в алгоритмы обучения, которые также ограничены, но всё же более мощные, чем любые, которые исследователи ранее понимали на столь строгом теоретическом уровне.

«Так или иначе, их самореферентный характер позволяет вам делать то, что, казалось бы, невозможно сделать с более стандартными проблемами», — сказал Иланго.

Результат привлёк внимание теоретиков сложности, работающих над другими темами. Он также стал предвестником дальнейших связей между метасложностью и сложностью среднего уровня, которые будут выявлены в ближайшие годы.

Прежде всего, это стало свидетельством того, как далеко могут продвинуться исследователи, задавая простые вопросы о препятствиях, которые на первый взгляд кажутся лишь препятствием на их пути.

«Такая двойственность прослеживается как минимум последние 30–40 лет, — сказал Импальяццо. — Препятствия часто становятся возможностями».

Частичный кредит

Прогресс только ускорился с тех пор, как Кармосино и его коллеги опубликовали свою статью.

«Происходит что-то новое, — сказала Колоколова. — Появляется много действительно талантливых молодых исследователей».

Иланго — один из таких молодых исследователей. За первые три года обучения в аспирантуре он взялся за решение сложной открытой проблемы доказательства NP-полноты MCSP, используя двухвекторную стратегию: доказательство NP-полноты для более простых версий MCSP, как это делали исследователи сложности схем, когда атаковали P против NP в 1980-х годах, а также доказательство NP-полноты для более сложных версий, которые интуитивно кажутся сложнее и, следовательно, их, возможно, легче доказать.

Иланго связывает свой интерес к метасложности с Эриком Аллендером, теоретиком сложности из Ратгерского университета и одним из немногих исследователей, продолжавших работать над метасложностью в 2000-х и начале 2010-х годов. «Его энтузиазм был заразителен», — сказал Иланго.

Еще один молодой исследователь, вдохновленный Аллендером, — Сюити Хирахара, ныне профессор Национального института информатики в Токио. Будучи аспирантом в 2018 году, Хирахара раскрыл истинную степень взаимосвязи между метасложностью и сложностью в среднем случае, обнаруженную Кармосино и его соавторами. Эти четверо исследователей обнаружили связь между сложностью в среднем случае одной задачи — MCSP — и сложностью в худшем случае другой — булевого обучения. Хирахара развил их методы, чтобы получить сокращение от худшего случая к среднему для MCSP. Его результат подразумевает, что гипотетический алгоритм MCSP в среднем случае, подобный тому, который рассматривали Кармосино и его коллеги, на самом деле будет достаточно мощным, чтобы решить немного другую версию MCSP без ошибок.

Результат Хирахары впечатляет, поскольку многие исследователи предполагают, что MCSP является NP-полной задачей, в отличие от всех других задач, для которых известны сокращения от худшего случая к среднему. Если им удастся распространить результаты Хирахары на все алгоритмы для среднего случая, а затем доказать, что MCSP является NP-полной задачей, это докажет, что мы живём не в эвристике.

«Это был бы поистине ошеломляющий результат», — сказал Сантанам.

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

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

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

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

«Это потрясающая работа», — сказал Уильямс. «Все считали, что эти частичные задачи примерно такой же сложности, как и полная задача».

Доказательство NP-полноты для полной версии MCSP по-прежнему сталкивается с препятствиями. Но ни одно из них не указывает на необходимость совершенно нового инструментария — возможно, дело лишь в поиске правильного способа объединения известных методов. Доказательство наконец определило бы статус одной из немногих задач, не поддающихся классификации с тех пор, как существует теория сложности. В электронном письме Левин написал: «Это бы меня смутило, если бы я показал свою глупость, не сумев этого заметить :-)».

Недостающие части

MCSP — не единственная проблема метасложности, которая привела к крупному прорыву. В 2020 году криптограф из Корнеллского технологического университета Рафаэль Пасс и его аспирант Яньи Лю обнаружили связь между другой проблемой метасложности и фундаментальным криптографическим протоколом, определяющим границу между «Эвристикой» и «Пессилендом», худшим из миров Импальяццо (где NP-полные задачи сложны в среднем смысле, но криптография всё ещё невозможна). Это делает изученную ими задачу главным кандидатом на атаку на «Пессиленд», а их более поздние исследования показывают, что она может быть использована и против «Эвристики».

«Не хватает некоторых фрагментов пазла, — сказал Пасс. — Для меня просто невероятно, насколько тесно эти области связаны».

Хирахара предупреждает, что исследователей, стремящихся отсеять миры, созданные Импальяццо 30 лет назад, ещё ждут трудности. «Я бы хотел сказать, что в какой-то момент Эвристика и Пессиланд будут исключены, но я не уверен, насколько мы близки к этому», — сказал он.

Многие исследователи ожидают, что наибольшей сложностью станет преодоление, казалось бы, безобидного разрыва между двумя разными моделями средней сложности. Криптографы обычно изучают алгоритмы, работающие в среднем случае, которые допускают ошибки в обоих направлениях, иногда ошибочно принимая случайные строки за псевдослучайные и наоборот. Между тем, предложенные Хирахарой методы сведения худшего случая к среднему работают для алгоритмов, работающих в среднем случае, которые допускают только первый тип ошибок. Такие тонкие различия могут иметь огромное значение в теории сложности. Но, несмотря на это и многие другие препятствия, Аллендер не может не высказывать сдержанный оптимизм.

«Я стараюсь не быть слишком уж самонадеянным, потому что есть довольно устоявшийся опыт, когда ничего не работает», — сказал он. «Но мы видим множество действительно интересных разработок — способов преодолеть то, что казалось препятствиями».

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

«На самом деле, даже здорово, что это так сложно, — сказал Кармозино. — Мне никогда не будет скучно».

Примечание редактора: Скотт Ааронсон является членом консультативного совета журнала Quanta Magazine.

Исправление: 21 августа 2023 г.
В более ранней версии этой статьи Леонид Левин был упомянут как аспирант, когда он помог открыть NP-полноту. В СССР он был эквивалентом студента.

Источник: www.quantamagazine.org