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

54

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

Следствие 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 за указание на это). В более общей ситуации, Свертывание экспирации и чередование ограниченных машин Тьюринга спрашивает, вызывает ли локальный коллапс на любом уровне в иерархии чередования коллапс вверх, как это происходит с иерархией полиномиального времени.

Андраш Саламон
источник
17
В качестве способа формализации языков в P, если P = NP, Риган ввел класс сложности H. Язык находится в H тогда и только тогда, когда L находится в P относительно каждого оракула так что P = NP . Таким образом, находится в H, если утверждение P = NP P релятивизируется. PH H Время чередования . Из теоремы Тоды и некоторых лемм в теореме Тоды также верно, что H P для каждого . (В принципе, любой оракул, удовлетворяющий PLOOOOLL(O(loglogn),poly)modqPqO = NP дает новую верхнюю границу H. Открыто ли H = PH.)O
Рассел Импальяццо
4
@ Рассел: спасибо! Этот комментарий звучит как ответ.
Андрас Саламон
5
Наконец, нашли ссылку на класс Кена Ригана : см. Определение 6.3 «Индексные наборы и представления классов сложности», доступное по адресу: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Официальная версия по адресу: dx.doi.org/10.1016/0304-3975(95)00146-8H
Джошуа
3
Пусть f (n) - любая неограниченная функция. H не содержится в Alternations-Time (f (n), poly), и если вы можете доказать, что P = NP подразумевает P = Alternations-Time (f (n), poly), то NP отличается от L.
Lance Fortnow

Ответы:

6

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

В качестве способа формализации языков в если , Риган ввел класс сложности . Язык в тогда и только тогда , когда находится в по отношению к каждому оракулу так , что . Таким образом, находится в если утверждение релятивизируется. PP=NPHLHLPOOPO=NPOLHP=NPLPPHHAltTime(O(lglgn),poly), Из теоремы Тоды и некоторых лемм в теореме Тоды также верно, что для каждого . По сути, любой оракул, удовлетворяющий дает новую верхнюю границу для . Открыто ли .HPmodqPqPO=NPOHH=PH

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

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

Для определения см. Определение 6.3 вH

Kaveh
источник
1
@ Джош, что касается комментария Ланса, я чувствую, что что-то упустил, так как не ограничено, а AltTime (f, poly) содержит H в соответствии с комментарием Рассела. f(n)=lglgn
Каве
3
Я запутался в чем-то. Почему ответ Джоша Грохова на предыдущий вопрос по этой теме ( cstheory.stackexchange.com/a/2039/1575 ) по существу не отвечает и на вопрос Риган? Т.е. почему он не приводит пример языка L, который находится в P, если P = NP по релятивизирующему аргументу, но не в PH, если P! = NP? И почему он не показывает, что если P! = NP, то H строго больше, чем PH?
Скотт Ааронсон
3
На самом деле, возможный ответ приходит ко мне. Является ли проблема в том, что в конструкции Грохова само определение языка L будет зависеть от оракула O?
Скотт Ааронсон
1
@ Скотт: Действительно, ваш возможный ответ правильный, так как какие строки используются для диагонализации (и, действительно, будут ли они вставлены в L или вне L), будет зависеть от оракула. Более подробно, если , язык конечен, поэтому разные для разных только конечно различны. Но если мы рассмотрим все такие, что , то для этих различных даже не может быть p-эквивалентным, поскольку этот набор оракулов является плотным подмножеством . PO=NPOLLOOPONPOLO2Σ
Джошуа
5

Как я уже писал в своем ответе на другой вопрос, давайте сделаем аргумент конструктивным и равномерным по числу чередований, предоставив алгоритм, который решает предполагая, что у нас есть алгоритм полиномиального времени для SAT, и посмотрим, что мы получим, если не является постоянным.ΣkPk

Пусть будет DTM с двумя входами и . Думайте об этом как о верификаторе проблемы .MxyNP

Пусть - это алгоритм, который преобразует TM в схему размера которая вычисляет на входах размера для шагов.Cook(M,n,t)Ms(n,t)polyMnt

Предположим, что и существует детерминированный алгоритм который решает проблему расширения сертификата Circuit-SAT за время .P=NPAppoly

С помощью этих ингредиентов мы определяем алгоритм для TQBF, который при заданной количественной булевой формуле рекурсивно удаляет самый внутренний квантификатор и заменяет его на свободный квантификатор. Пусть будет размером формулы на м шаге, тогда мы имеем . Если формула имеет квантификаторов, мы получим где - размер формулы TQBF, заданной в качестве входных данных.siisi+1=sp(si)kq(n)=(sp)k(n)n

Если константа, то . Поскольку значение схемы находится в у нас есть алгоритм за полиномиальное время.kq(n)polyP

Если то больше не является полиномиальным временем, мы получаем алгоритм, который находится в . Например, если мы получаем алгоритм квазиполиномиального времени. Для мы не получаем ничего нетривиального.kω(1)q(n)n2O(k)k=lglgnk=lgn


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

TP=NPP=C
TZFCPNP

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


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

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

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