Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Эта полиномиальная иерархия в самом деле представляет собой существенное обобщение NP и co-NP — в том смысле, что даже если бы у нас был оракул для NP-полных задач, совершенно неясно, как мы бы могли использовать его для решения, скажем, Σ2P-задач. С другой стороны, я утверждаю (просто для того, чтобы еще усложнить ситуацию), что если P = NP, то вся полиномиальная иерархия схлопнется до одного P! Почему?

Верно: если P = NP, то мы могли бы взять наш алгоритм для решения NP-полных задач за полиномиальное время и модифицировать его так, чтобы он вызывал сам себя в качестве подпрограммы. И это позволило бы нам «сплющить PH паровым катком»: сначала смоделировать NP и co-NP, затем Σ2P и Π2P и т. п. по всей иерархии.

Подобно этому несложно доказать, что если NP = co-NP, то вся полиномиальная иерархия схлопнется до NP (или, иными словами, до co-NP). Если Σ2P = Π2P, то вся полиномиальная иерархия схлопнется до Σ2P, и так далее. Если немного подумать, это дает нам целую бесконечную последовательность обобщений гипотезы P ≠ NP, таких, что каждую последующую доказать «труднее», чем предыдущую. Почему нас вообще интересуют эти обобщения? Потому что часто случается так, что при изучении некоторой гипотезы с условным именем Ля-ля мы не можем доказать, что Ля-ля верна, и не можем даже доказать, что если бы Ля-ля была неверна, то P был бы равен NP. Но — и в этом вся изюминка — мы можем доказать, что если бы Ля-ля была неверна, то полиномиальная иерархия схлопнулась бы до второго или третьего уровня. А это некоторый аргумент в пользу того, что Ля-ля все-таки верна.

В общем, добро пожаловать в теорию вычислительной сложности!

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

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

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

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

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

Таким образом, наша цель как коллективной свахи состоит в том, чтобы найти стабильный способ переженить их всех с учетом заданных предпочтений мужчин и женщин.

Первый очевидный вопрос: всегда ли существует стабильный вариант распределения мужчин и женщин на пары? Как вы считаете? Да? Нет? Оказывается, такое распределение существует, но простейший способ доказать это — просто дать алгоритм его нахождения!

Давайте сосредоточимся на вопросе о том, как найти такой вариант. В целом существует N! способов распределения наших женихов и невест по парам. И надо надеяться, хотя бы ради наших потенциальных новобрачных, что нам не придется перебирать их все.

К счастью, действительно не придется. В начале 1960-х гг. Гейл и Шейпли придумали алгоритм полиномиального — более того, линейного — времени для решения этой задачи. Прелесть его в том, что он в точности соответствует варианту, который вы могли бы предложить, начитавшись викторианских любовных романов. Позже они обнаружили, что этот самый алгоритм уже используется с 1950-х гг., но не для организации массовых бракосочетаний, а для распределения студентов-медиков по больницам на интернатуру. Мало того, больницы и медицинские школы до сих пор пользуются одной из версий этого алгоритма.

Но вернемся к нашим мужчинам и женщинам. Если мы хотим переженить их всех при помощи алгоритма Гейла — Шейпли, то в качестве первого шага нам нужно нарушить симметрию между полами и решить: какой пол «делает предложение»? Поскольку дело происходило в начале 1960-х гг., можете сами представить, каким был ответ. Предложение всегда делали мужчины.

Таким образом, мы проходим цикл по всем мужчинам. Первый мужчина делает предложение той женщине, которая больше всего ему понравилась. Она временно принимает предложение. Затем следующий мужчина делает предложение женщине, которая у него стоит «первой в списке». Она временно принимает предложение и т. п. Но что происходит, когда мужчина делает предложение женщине, которая уже, хотя и временно, приняла предложение другого мужчины? В этом случае она выбирает из них того, кто ей больше нравится, и дает второму отставку! Когда мы в следующий раз дойдем до этого мужчины в процессе циклического перебора всех мужчин, он сделает предложение женщине, которая стояла в его списке второй. И если она его отвергнет, то в третий раз, когда мы до него доберемся, он сделает предложение третьей в списке женщине. И так далее, пока все не переженятся. Просто, не правда ли?

Первый вопрос: почему этот алгоритм завершается за линейное время?

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

Второй вопрос: почему, когда алгоритм завершает работу, все оказываются состоящими в браке?

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