Каковы естественные примеры нерелятивизируемых доказательств?

13

Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии).

Практически все доказательства кажутся релятивизируемыми.

Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству было бы нужно быть, что не являются тривиальными или надуманными?

(Я не теоретик рекурсии, поэтому прошу прощения за отсутствие цитат.)

[РЕДАКТИРОВАТЬ: лучше сообщение Mathoverflow ]

Sai
источник
6
Чтобы скопировать мое предложение от МО и убрать его с пути: канонический пример, который я знаю, является доказательством IP = PSPACE, где, в частности, включение PSPACE в IP осуществляется путем показа интерактивного доказательства для конкретного PSPACE. - неполная проблема, нерелятивизируемая техника - конкретные проблемы не релятивизируются.
Стивен Стадницки
5
@AndrejBauer AFAIK, нет, потому что нет такой вещи, как «релятивизированный TQBF» - на самом деле, есть оракулы с I P AP S PA , поэтому доказательство не может канонически релятивизироваться. IPAPSPACEA
Стивен Стадницки
4
@Steven: Релятивизированный TBQF может быть сформирован путем использования ворот оракула, а не только (стандартных) логических ворот.
3
@RickyDemer Тем не менее, сердце доказательства работает, интерпретируя формулу как полином низкой степени, который не проходит, когда у вас есть (скажем) равномерно случайные врата оракула.
Йонатан N
1
Кстати, результат P =? NP по релятивизации известен как теорема Бейкера-Гилла-Соловая 1975 года . доказательство также можно найти, например, в Hopcroft / Ullman . @ richerby / Sai нет причин мигрировать после того, как оба вопроса уже введены, это больше для дальнейшего использования. Также обратите внимание, что, как представляется, не существует официальной межсайтовой политики в отношении стекового обмена на кросспостинге (поэтому некоторая путаница понятна).
vzn

Ответы:

24

Как Стивен примечаний, канонический пример . Этот коллапс не релятивизируется, в том смысле, что существует оракул A , подчиняющийся I P AP S P A C E AIP=PSPACEAIPAPSPACEA . Интуиция, почему известное доказательство этого результата избегает барьера релятивизации, состоит в том, что он использует арифметизацию (Йонатан упомянул об этом в комментарии): интерактивный протокол для PSPACE- неполная задача TQBF задается путем рассмотрения расширения количественной булевой формулы до полинома низкой степени над достаточно большим полем. Если нам дать релятивизированную булеву формулу (с вратами оракула), такого расширения не существует.

Из-за Ааронсона и Вигдерсона происходит уточнение барьера релятивизации - алгебрирования . В общем, метод арифметизации недостаточен, чтобы обойти барьер алгебраизации. Класс сложности включение algebrizes , если для любого оракула А и любого расширения ~ A от A до низкой степени многочленов над конечным полем, C AD ~ A . Разделение CD алгебрирует, если для всех A и всех расширений ˜ A , CCDAA~ACADA~CDAA~ . Ааронсон и Вигдерсон показывают, что I P = P S P A C E E алгебризирует, но многие другие результаты, включая N P P , нет.CA~DAIP=PSPACENPP

Недавний пример методики , которая не algebrize или релятивизировать является доказательством Райана Уильямса , что . Разделение не алгебрирует: существует оракул A и расширение ˜ A низкой степени, такое что N E X PNEXPACCAA~. Интуитивно понятно, что доказательство позволяет избежать барьера в том, что оно основано на существовании более быстрого, чем тривиальный алгоритм выполнимости дляACCNEXPA~ACCAACCсхемы, и алгоритм использует нерелятивизирующие и неалгебрирующие свойства таких схем. Райан отмечает в статье, что все известные более быстрые, чем тривиальные алгоритмы выполнимости ломаются при добавлении оракулов или алгебраических расширений оракулов.

Существует также интересный подход к пониманию релятивизации через логику. В старой рукописи Арора, Импальяццо и Вазирани определяют систему аксиом так, что релятивизирующие результаты являются именно теми, которые следуют из аксиом, а нерелятивизирующие результаты не зависят от системы. В работе Impagliazzo, Kabanets и Kolokolova что-то похожее для алгебризации вводится дополнительная аксиома к тем, которые определены Arora, Impagliazzo и Vazirani Они показывают, что большинство известных нерелятивизирующих результатов вытекают из их аксиом, в то время как P против NP, помимо прочего, не зависит от них.

Извиняюсь, если я что-то не так понял, я не совсем эксперт.

Сашо Николов
источник
7
NEXPMIPMAEXPP/polyPromiseMASIZE(nk)
10

Вот список нерелятивизируемых доказательств:

  1. Теорема PCP

  2. Обязательства, зависящие от экземпляра, подразумевают протокол с нулевым знанием:
    эквивалентность между нулевым знанием и обязательствами

  3. Не существует эффективного обфускатора виртуальных «черных ящиков» для общих схем:
    эквивалентность нулевого знания и обязательств

  4. S5

  5. Против незапутанных проверяющих, NEXP имеет минимально интерактивные системы проверки с двумя доказательствами: системы с
    двумя испытаниями с одним доказательством: их сила и проблемы

  6. Против возможных запутанных средств проверки NEXP имеет более интерактивные протоколы MIP:
    интерактивное доказательство с несколькими доказательствами для звука NEXP против запутанных средств проверки

  7. ), а затем «NISZK» из предыдущего предложения может быть заменен на «NIPZK».
    Джонатан Кац, продвинутые темы в криптографии, лекция 13
    Ciπ если бы он был не в состоянии выбрать элемент из {0,1,2,3, ..., n! -1} совершенно равномерно за достаточно малое время, так как такой выбор позволил бы создать совершенно равномерную генерацию матрица ориентированного цикла графа или перестановка вершин.

Кава
источник
7

Это хороший обзор области, проведенный ведущим экспертом, который суммирует / детализирует некоторые пункты других ответов до сих пор и имеет дополнительные примеры.

[1] Роль релятивизации в теории сложности Fortnow

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

ВЗН
источник
6
+1 это хороший опрос, но следует упомянуть, что он изучает состояние мира до 1993 года
Сашо Николов
правда; было бы полезно, если бы авторы включили даты в свои статьи больше ... более недавний опрос также был бы полезен, тема, кажется, редко исследуется. эта область, кажется, не меняется так сильно, и не очень ясно, сколько новых результатов появилось с этой даты.
vzn
3
для новых результатов: я думаю, что некоторые новые результаты оракула появились с тех пор, которые относятся к классам квантовой сложности. что еще более важно, были события с точки зрения того, что означают результаты оракула: барьер алгебраизации и неалгебризирующее доказательство Райана из моего ответа, связанная статья cs.sfu.ca/~kabanets/papers/act-full.pdf и, возможно, Работа Боаза Барака по сокращению криптографии без черного ящика.
Сашо Николов