Какова «реальная» причина того, что IP = PSPACE является нерелятивизирующим?

$O$ ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

Тем не менее, я видел только несколько человек, которые дают «прямое» объяснение того, почему результат не релятивизируется, и обычный ответ - «арифметизация». После проверки доказательства IP = PSPACE этот ответ не является ложным , но он не является удовлетворительным для меня. Кажется, что «реальная» причина прослеживается в доказательстве того, что задача TQBF - истинная квантифицированная логическая формула - является полной для PSPACE; Чтобы доказать это, вам нужно показать, что вы можете кодировать конфигурации машины PSPACE в формате полиномиального размера, и (это кажется нерелятивизирующей частью) вы можете кодировать «правильные» переходы между конфигурациями в полиномиальном размере логическая формула - здесь используется шаг в стиле Кука-Левина. ${\sf IP} = {\sf PSPACE}$

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

Мне кажется, это является основной причиной того, что IP = PSPACE является нерелятивизирующим; и фольклорная мантра о том, что методы арифметизации не релятивизируются, кажется побочным продуктом этого: единственный способ арифметизировать что-то - это если у вас есть логическая формула, которая кодирует что-то о ТМ в первую очередь!

Я что-то упускаю? В качестве подвопроса - означает ли это, что все результаты, которые каким-либо образом используют TQBF, также не релятивизируются?

cc.complexity-theory interactive-proofs relativization Генри Юн
источник

Вы можете включить ворота оракула в количественную булеву формулу, и тогда такой релятивизированный TQBF ^ O будет завершен для PSPACE ^ O, так что это не нерелятивизирующий шаг.

Эмиль Йержабек поддерживает Монику

Привет, Эмиль. Не могли бы вы рассказать подробнее? Допустим, у меня есть машина M, и я пытаюсь выполнить то же доказательство того, что L (M) (язык, принятый M) сводится к (что бы ни ). В конце концов мне придётся придумать булеву формулу, которая выражает, являются ли две конфигурации C, C 'машины-оракула M соседними (для любых двух конфигураций C, C'). Как я могу гарантировать, что независимо от оракула эта логическая формула имеет конечный размер, не говоря уже о полиномиальном размере? Например, O может закодировать проблему остановки.

{P S P A C E}^{O}

${\sf PSPACE}^O$

T B Q F^{O}

$TBQF^O$

T B Q F^{O}

$TBQF^O$

Генри Юн

Я думаю, что я мог бы отодвинуть это еще дальше - релятивизируется ли сама теорема Кука-Левина ? По тем же причинам, упомянутым выше, я не думаю, что это так. Относится ли релятивизация к теореме Кука-Левина и релятивизирует ли доказательство полноты PSPACE для TQBF.

Генри Юн

Формула QBF ^ O может, помимо обычных квантификаторов и логических связок, также использовать новые неограниченные веерные вентили, назовем их , семантика которых заключается в том, что тогда и только тогда строка принадлежит к оракулу . Выражение на этом языке того, что одна конфигурация является преемницей другой, является простым упражнением, поскольку вы можете просто вставить содержимое ленты запроса оракула в . (Я предполагаю, что машина PSPACE может выполнять полиномиально длинные запросы.)

f (x_{0}, \dots, x_{n})

$f(x_0,\dots,x_n)$

f (x_{0}, \dots, x_{n}) = 1

$f(x_0,\dots,x_n)=1$

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$

Эмиль Йержабек поддерживает Монику

Я вижу - вы говорите, что когда вы релятивизируете доказательство полноты TQBF в PSPACE, вы не только релятивизируете машины в игре, но вы также релятивизируете сами булевы формулы (так что они больше не являются булевыми формулами в строгом смысле). ). В этом случае я могу понять, почему шаг арифметизации сломался. Благодарность! Возможно, вы можете написать это как ответ.

Генри Юн

Любой ответ на вопрос формы «Какова реальная причина этого…» обязательно будет несколько субъективным. Тем не менее, для конкретного случая IP = PSPACE, я думаю, что можно привести довольно хороший пример того, что арифметизация действительно является ключом, наблюдая, что хотя IP = PSPACE не релятивизируется , он алгебрирует в смысле Ааронсона и Вигдерсона . Как они объясняют в своей статье, грубо говоря, включение класса сложности алгебризирует, если для всех оракулы и все расширения низкой степени из ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ $A$ , В частности, они показывают, что включение PSPACE IP алгебрирует, даже если оно не релятивизируется. $\subseteq$

Интуиция, которую я разработал, заключается в том, что нерелятивизирующие результаты - это те, которые бьют по мелочам Тьюринга.

Это не плохая интуиция, но я думаю, что результат Ааронсона-Вигдерсона показывает, что доказательство IP = PSPACE показывается довольно ограниченным образом и, конечно, не достаточно изощренным способом доказать P NP, так как Ааронсон и Вигдерсон также показывают, что неалгебризационные методы потребуются для отделения P от NP. $\ne$

Тимоти Чоу
источник

Спасибо за ссылку. Позвольте мне понять, понимаю ли я это: то, что вы - и статья Ааронсона / Вигдерсона - похоже, утверждаете, - это то, что «арифметизация» является слабо нерелятивизирующим шагом и что крошечное, естественное изменение понятия релятивизации (а именно, алгебраическая релятивизация) нарушит это свойство. Поскольку остальные доказательства IP = PSPACE являются релятивизирующими (и я убежден тем, что сказал Эмиль выше), это означает, что сам результат IP = PSPACE очень слабо нерелятивизирующий, как вы и сказали. Очень интересно! Благодарю. Мне нужен способ принять оба ответа :)

Генри Юн

Да, это в основном правильно.

Тимоти Чоу

Какова «реальная» причина того, что IP = PSPACE является нерелятивизирующим?

Ответы: