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

k по нашему выбору). Это пример релятивизирующих рассуждений, поскольку мы не обращали внимания на то, имеют эти схемы какие бы то ни было оракулы или нет. Чтобы применить эти рассуждения не к P#P, а к меньшему классу PP, нам пришлось использовать нерелятивизирующий компонент, а именно результат интерактивного доказательства по LFKN.

Но действительно ли это дает нам нижнюю оценку для нерелятивизирующей схемы? То есть существует ли оракул, относительно которого PP имеет схемы линейного размера? Много лет назад мне удалось построить такой оракул[138]. Это показывает, что результат Винодчандрана был нерелятивизирующим, — в самом деле, это один из немногих в теории сложности примеров неоспоримо нерелятивизирующего разделения. Иными словами, барьер релятивизации — один из главных препятствий в доказательстве P ≠ NP — может быть преодолен в некоторых очень ограниченных случаях.

Новые достижения

Во всяком случае, именно так обстояли дела, когда я в первый раз писал эту главу в 2006 г. С тех пор появились кое-какие очень интересные новости. Во-первых, в 2007 г. Рахул Сантханам[139] улучшил результат Винодчандрана и показал, что PromiseMA — класс всех задач с априорными ограничениями на входные данные с протоколами доказательства от Мерлина — Артура — не имеет схем размера nk для любого фиксированного k.

Вскоре после этого мы с Ави Вигдерсоном[140], вдохновленные результатом Сантханама, открыли новое препятствие к дальнейшему развитию теории сложности, которое мы назвали алгебраизацией. По существу, алгебраизация расширяет уже имевшийся барьер релятивизации по Бейкеру, Гиллу и Соловею в том, что когда мы изучаем вопрос о классах сложности относительно некоторого оракула A, мы теперь обеспечиваем одному из классов сложности доступ к «полиномиальному расширению невысокой степени» от A вместо самого A. Этот более мощный тип доступа к оракулу дает нам некоторый дополнительный рычаг воздействия; в частности, он позволяет нам сымитировать все стандартные нерелятивизирующие результаты, основанные на арифметизации. К примеру, хотя (как мы уже обсуждали) неверно, что IPA = PSPACEA для любого оракула A, тем не менее верно PSPACEA ⊆ IP~A, где ~A означает многочлен невысокой степени над большим конечным полем, который оказывается равным A, если получает на вход только булевы строки. Таким образом, мы говорим, что теорема IP = PSPACE «алгебраизирует», хотя и не релятивизирует. С другой стороны, мы с Ави показали также, что для большинства знаменитых открытых задач, включая не только «P или NP», но и «P или BPP», «NEXP или P/poly» и др., любое решение потребует «неалгебраизирующих методик», которые не проходят даже для этих новых алгебраических оракулов в том же смысле, в каком теорема IP = PSPACE не выполняется по отношению к обычным оракулам. Так что сухой остаток в том, что возможности методик, использованных для прорывных открытий с интерактивными доказательствами, тоже ограничены: конечно, они позволяют обойти барьер релятивизации, но лишь для того, чтобы воткнуться на полном ходу в барьер «обобщенной» релятивизации, ожидающий несколькими шагами дальше.

Существуют ли методики поиска нижней грани, позволяющие обойти как барьер релятивизации, так и барьер алгебраизации? Да; мало того, они известны уже не один десяток лет.

В начале 1980-х гг. Фурст, Сакс и Сипсер[141], а также (независимо) Айтаи[142] открыли революционную методику поиска нижних граней для размеров схем постоянной глубины (constant-depth circuits), к примеру схем AC0, состоящих из вентилей и, или и не, организованных в O (1) слои (где каждый вентиль и и или может иметь произвольное число входов). Фурст с соавторами и Айтаи показали, что для определенных функций, таких как четность n бит, любая схема AC0 должна иметь экспоненциальное число вентилей. Поскольку все участники активно использовали методы комбинаторики — в их основе лежало наблюдение за поведением реальных отдельных вентилей, — им удалось обойти барьер релятивизации. С тех пор аналогичными методами были доказаны и другие нижние оценки; особенно интересны работы Разборова[143] и Смоленского[144] для схем AC0, дополненных способностью к выполнению арифметических операций по модулю p (где p — некоторое фиксированное простое число).

К сожалению, в 1993 г. Разборов и Рудич указали[145], что почти все нижние оценки «комбинаторного типа» натыкаются на барьер, который они назвали «естественными доказательствами», — в некоторых отношениях он является дополнительным к барьеру релятивизации. Суть дела в двух словах: при применении комбинаторных методов поиска нижних оценок показывается, что определенные функции (к примеру, PARITY) являются трудными для небольших схем, потому что эти функции «похожи на случайные функции» в некотором эффективно вычислимом отношении, тогда как всякая функция, вычисляемая небольшой схемой должна выглядеть неслучайной в этом отношении. Однако любой аргумент такого сорта можно перевернуть с ног на голову и использовать для отличения «по-настоящему» случайных функций от псевдослучайных, решая таким образом, по иронии судьбы, некоторые из тех самых задач, трудность которых мы хотели доказать! Рассуждения Фурста и Ажтаи сработали именно потому, что схемы AC0 слишком слабы для вычисления псевдослучайных функций, мало того, невозможность псевдослучайности в AC0 может быть выведена как следствие доказательств нижней оценки. Но мы не можем ожидать, что какие-то аналогичные рассуждения сработают при доказательстве нижних оценок против более мощных классов схем, таких как P/poly, считая, как считает огромное большинство из нас, что эти классы и правда имеют псевдослучайные функции. (Говоря языком плаката, именно факт вычислительной трудности делает доказательство вычислительной трудности таким трудным!) Более того, Наор и Рейнгольд показали[146], что при правдоподобных криптографических допущениях даже класс TC0, состоящий из схем постоянной глубины с мажоритарными вентилями, способен вычислять псевдослучайные функции. Так что барьер естественных доказательств по Разборову — Рудичу, похоже, действительно выходит на сцену всего лишь «чуть» выше AC0.

Если вы хотите избежать барьера естественных доказательств, вам, судя по всему, потребуются методики, «пристрелянные» к некоторому особому свойству функции f, трудность которой вы пытаетесь доказать, — к свойству, которое не является общим для f и некоторой случайной функции. Очевидный пример методики, и правда сосредоточенной на таком особом свойстве, — «диагонализация», методика, какой мы пользовались ранее для доказательства того, что P#P не имеет схем линейного размера. (Вспомните, что наше доказательство пользовалось способностью #P-машины моделировать всевозможные схемы линейного размера и избегать моделирования со стороны любой из них.) Увы, но хотя такого рода методики позволяют обойти барьер естественного доказательства, именно они как раз и не позволяют обойти барьер релятивизации! Я имею в виду: