Можно ли усилить P = NP за пределами P = PH?

В описательной сложности Иммерман имеет

Следствие 7.23. Следующие условия эквивалентны:
1. P = NP.
2. Над конечными упорядоченными структурами FO (LFP) = SO.

Это можно рассматривать как «усиление» P = NP до эквивалентного утверждения над (предположительно) классами большей сложности. Обратите внимание, что SO захватывает иерархию PH полиномиального времени, а FO (LFP) захватывает P, поэтому это можно рассматривать как P = NP, если P = PH.

(Интересной частью этого является утверждение, что P = NP подразумевает P = PH; тривиально, что P = CC подразумевает P = NP для любого класса CC, содержащего NP. Иммерман просто замечает: «если P = NP, то PH = NP» , предположительно потому, что P = NP может использоваться с оракуловым определением PH, чтобы индуктивно показать, что вся иерархия разрушается.)

Мой вопрос:

Насколько дальше можно усилить P = NP таким образом?

В частности, какой самый большой известный класс CC 'такой, что P = NP подразумевает P = CC', а самый маленький класс CC такой, что P = NP подразумевает CC = NP? Это позволило бы заменить P = NP эквивалентным вопросом CC = CC '. P представляется довольно мощным классом, который, кажется, предоставляет небольшую «комнату для маневра» для аргументов, пытающихся отделить его от NP: как далеко можно увеличить комнату для маневра?

Я, конечно, также был бы заинтересован в аргументе, который показывает, что P = PH является пределом этого подхода.

Изменить: обратите внимание на тесно связанный вопрос Почему P = NP не подразумевает P = AP (то есть P = PSPACE)? который фокусируется на другом направлении, почему у нас нет доказательств того, что P = PSPACE. Ответы там Каве и Питера Шора утверждают, что количество фиксируемых чередований является ключевым. Другой связанный с этим вопрос - это проблема решения, которая, как известно, не находится в PH, но будет в P, если P = NP, который запрашивает потенциальную проблему; ответы там также могут быть использованы для построения ответов на этот вопрос, хотя эти классы несколько искусственны (спасибо Tsuyoshi Ito за указание на это). В более общей ситуации, Свертывание экспирации и чередование ограниченных машин Тьюринга спрашивает, вызывает ли локальный коллапс на любом уровне в иерархии чередования коллапс вверх, как это происходит с иерархией полиномиального времени.

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy Андраш Саламон
источник

Связанный (бесстыдное самореклама): проблема решения, которая, как известно, не находится в PH, но будет в P, если P = NP .

Tsuyoshi Ito

В качестве способа формализации языков в P, если P = NP, Риган ввел класс сложности H. Язык находится в H тогда и только тогда, когда L находится в P относительно каждого оракула так что P = NP . Таким образом, находится в H, если утверждение P = NP P релятивизируется. PH H Время чередования . Из теоремы Тоды и некоторых лемм в теореме Тоды также верно, что H P для каждого . (В принципе, любой оракул, удовлетворяющий P

L

$L$

^{O}

$^O$

O

$O$

^{O}

$^O$

^{O}

$^O$

L

$L$

⟹ L \in

$\implies L \in$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

(O (\log \log n), p o l y)

$(O(\log \log n), \rm{poly})$

\subseteq

$\subseteq$

^{{m o d}_{q} P}

$^{\rm{mod}_q \rm{P}}$

q

$q$

^{O}

$^O$ = NP дает новую верхнюю границу H. Открыто ли H = PH.)

^{O}

$^O$

Рассел Импальяццо

@ Рассел: спасибо! Этот комментарий звучит как ответ.

Андрас Саламон

Наконец, нашли ссылку на класс Кена Ригана : см. Определение 6.3 «Индексные наборы и представления классов сложности», доступное по адресу: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Официальная версия по адресу: dx.doi.org/10.1016/0304-3975(95)00146-8

H

$H$

Джошуа

Пусть f (n) - любая неограниченная функция. H не содержится в Alternations-Time (f (n), poly), и если вы можете доказать, что P = NP подразумевает P = Alternations-Time (f (n), poly), то NP отличается от L.

Lance Fortnow

Ответы:

Из комментария Рассела Импальяццо :

В качестве способа формализации языков в если , Риган ввел класс сложности . Язык в тогда и только тогда , когда находится в по отношению к каждому оракулу так , что . Таким образом, находится в если утверждение релятивизируется. $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{H}$ $L$ $\mathsf{H}$ $L$ $\mathsf{P}^O$ $O$ $\mathsf{P}^O=\mathsf{NP}^O$ $L$ $\mathsf{H}$ $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$ , Из теоремы Тоды и некоторых лемм в теореме Тоды также верно, что для каждого . По сути, любой оракул, удовлетворяющий дает новую верхнюю границу для . Открыто ли . $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ $q$ $\mathsf{P}^O=\mathsf{NP}^O$ $\mathsf{H}$ $\mathsf{H}=\mathsf{PH}$

И из комментария Ланса Фортнау :

Пусть - любая неограниченная функция. не содержится в и если вы можете доказать, что подразумевает затем отличается от . $f(n)$ $\mathsf{H}$ $\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{NP}$ $\mathsf{L}$

Для определения см. Определение 6.3 в $\mathsf{H}$

Кеннет В. Риган, " Наборы указателей и презентации классов сложности ", 1999

Kaveh
источник

@ Джош, что касается комментария Ланса, я чувствую, что что-то упустил, так как не ограничено, а AltTime (f, poly) содержит H в соответствии с комментарием Рассела.

f (n) = \lg \lg n

$f(n) = \lg \lg n$

Каве

Я запутался в чем-то. Почему ответ Джоша Грохова на предыдущий вопрос по этой теме ( cstheory.stackexchange.com/a/2039/1575 ) по существу не отвечает и на вопрос Риган? Т.е. почему он не приводит пример языка L, который находится в P, если P = NP по релятивизирующему аргументу, но не в PH, если P! = NP? И почему он не показывает, что если P! = NP, то H строго больше, чем PH?

Скотт Ааронсон

На самом деле, возможный ответ приходит ко мне. Является ли проблема в том, что в конструкции Грохова само определение языка L будет зависеть от оракула O?

Скотт Ааронсон

@ Скотт: Действительно, ваш возможный ответ правильный, так как какие строки используются для диагонализации (и, действительно, будут ли они вставлены в L или вне L), будет зависеть от оракула. Более подробно, если , язык конечен, поэтому разные для разных только конечно различны. Но если мы рассмотрим все такие, что , то для этих различных даже не может быть p-эквивалентным, поскольку этот набор оракулов является плотным подмножеством .

P^{O} = N P^{O}

$P^O = NP^O$

L

$L$

L

$L$

O

$O$

O

$O$

P^{O} \neq N P^{O}

$P^O \neq NP^O$

L

$L$

O

$O$

2^{Σ^{*}}

$2^{\Sigma^*}$

Джошуа

Как я уже писал в своем ответе на другой вопрос, давайте сделаем аргумент конструктивным и равномерным по числу чередований, предоставив алгоритм, который решает предполагая, что у нас есть алгоритм полиномиального времени для SAT, и посмотрим, что мы получим, если не является постоянным. $\Sigma^P_k$ $k$

Пусть будет DTM с двумя входами и . Думайте об этом как о верификаторе проблемы . $M$ $x$ $y$ $\mathsf{NP}$

Пусть - это алгоритм, который преобразует TM в схему размера которая вычисляет на входах размера для шагов. $Cook(M, \vec{n}, t)$ $M$ $s(\vec{n},t) \in \mathsf{poly}$ $M$ $\vec{n}$ $t$

Предположим, что и существует детерминированный алгоритм который решает проблему расширения сертификата Circuit-SAT за время . $\mathsf{P}=\mathsf{NP}$ $A$ $p\in\mathsf{poly}$

С помощью этих ингредиентов мы определяем алгоритм для TQBF, который при заданной количественной булевой формуле рекурсивно удаляет самый внутренний квантификатор и заменяет его на свободный квантификатор. Пусть будет размером формулы на м шаге, тогда мы имеем . Если формула имеет квантификаторов, мы получим где - размер формулы TQBF, заданной в качестве входных данных. $s_i$ $i$ $s_{i+1} = s\circ p(s_i)$ $k$ $q(n) = (s \circ p)^k(n)$ $n$

Если константа, то . Поскольку значение схемы находится в у нас есть алгоритм за полиномиальное время. $k$ $q(n) \in \mathsf{poly}$ $\mathsf{P}$

Если то больше не является полиномиальным временем, мы получаем алгоритм, который находится в . Например, если мы получаем алгоритм квазиполиномиального времени. Для мы не получаем ничего нетривиального. $k \in \omega(1)$ $q(n)$ $n^{2^{O(k)}}$ $k = \lg \lg n$ $k = \lg n$

Я думаю, что нас действительно интересует самый большой класс такой что где - достаточно сильная теория, чтобы формализовать все наши текущие результаты (например, вы можете считать это ), потому что основной смысл этих результатов заключается в упрощении доказательства . $C$

T ⊢ P = N P \to P = C

$T \vdash \mathsf{P} = \mathsf{NP} \to \mathsf{P}=C$

T

$T$

Z F C

$\mathsf{ZFC}$

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

Если мы возьмем более слабые теории результат все еще может быть интересно, но это на самом деле не верхняя граница наибольшего значения . Когда Риган использует релятивизацию для определения он по существу ограничивает аргументы теми, которые релятивизируются. Если мы используем результат, который не релятивизируется, мы можем получить больший класс, чем , который будет равен если . $C$ $\mathsf{H}$ $\mathsf{H}$ $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$

В качестве более философской заметки мне лично не нравится идея думать о релятивизации как об альтернативных реальностях или мирах. Утверждения в «релятивизированных мирах» сами по себе не дают нам никакой информации об утверждении в нерелятивизированной обстановке. В качестве примера этого возьмем который большинство из нас не считает верным, но релятивизированная версия является истинной, со случайным оракулом с вероятностью 1. В качестве другого примера возьмем который является истинным, но становится ложным относительно случайного оракула с вероятностью 1. $\mathsf{BPP} = \mathsf{PP}$ $\mathsf{IP} = \mathsf{PSpace}$

Я также нахожу идею, что существует только один правильный способ релятивизации класса сложности, проблематичный, который вызывает много неправильных представлений (например, релятивизация мышления как функциональная операция над классами сложности в их экстенсиональном смысле, релятивизация - это модификация модели вычислений). , а не класс функций или языков). Я думаю, что просмотр релятивизаций как модифицированных (интерактивных) вычислительных сред более полезен. Таким образом, есть много полезных способов релятивизации классов сложности (в его намеренном смысле). Чтобы получить любую информацию о нерелятивизированном сеттинге из релятивизированной структуры, нам нужен какой-то принцип переноса, аналогичный принципу переноса в нестандартном анализе., Обратите внимание, что выбор определенного метода релятивизации для классов, которые сохраняют известные отношения между классами, не дает нам принцип переноса (это основные критерии, которые обычно используются в литературе для определения «правильной» релятивизации класса).

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

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

Томас Климпел