Решение проблемы, которая, как известно, не находится в PH, но будет в P, если P = NP

Изменить : Как правильно указал Рави Боппана в своем ответе, и Скотт Ааронсон также добавил еще один пример в своем ответе , ответ на этот вопрос оказался «да» таким образом, которого я вообще не ожидал. Сначала я подумал, что они не ответили на вопрос, который я хотел задать, но, подумав, эти конструкции отвечают, по крайней мере, на один из вопросов, которые я хотел задать, а именно: «Есть ли способ доказать условный результат?» P = NP ⇒ L ∈P 'без доказательства безусловного результата L ∈PH? ”Спасибо, Рави и Скотт!

Существует ли проблема решения L такая, что выполняются оба следующих условия?

L, как известно, не находится в полиномиальной иерархии.
Известно, что P = NP влечет L ∈P.

Искусственный пример так же хорош, как и естественный. Кроме того, хотя я использую букву « L », это может быть проблемой обещания вместо языка, если это помогает.

Фон . Если мы знаем, что решающая задача L находится в полиномиальной иерархии, то мы знаем, что «P = NP ⇒ L ∈P». Цель вопроса состоит в том, чтобы спросить, верно ли обратное. Если существует язык L, удовлетворяющий двум вышеуказанным условиям, то его можно рассматривать как доказательство того, что обратное утверждение неверно.

Этот вопрос мотивирован интересным комментарием Джо Фитцсимонса к моему ответу на вопрос Уолтера Бишопа « Последствия #P = FP ».

cc.complexity-theory conditional-results np polynomial-hierarchy Цуёси Ито
источник

Доказать универсальный негатив всегда сложно (э), но я был бы удивлен, если бы такой язык существовал. Обобщенная гипотеза Линиала-Нисана (если бы она оказалась верной) не подразумевала бы, что вы спрашиваете, я не верю. Это просто означало бы, что BQP не содержится в PH. Если бы PH рухнул на P, BQP все равно не содержался бы в P (H).

Даниэль Апон

Вы спрашиваете, существует ли класс сложности X st X не является подмножеством PH, а P = NP -> X = P?

Филипп Уайт

@Philip: Да, но я не думаю, что это меняет проблему, потому что мы обычно можем преобразовать проблему решения L в класс X проблем решения, сводимых к L. По крайней мере, я хотел задать этот вопрос с точки зрения проблем с решением. ,

Цуёси Ито

Может быть, вы хотите потребовать, чтобы язык

был как-то близок к PH, в дополнение к вашим текущим требованиям? Может быть, скажем, в PSPACE (хотя это спорно , насколько близко PSPACE является PH, см S. Феннер, С. Гомера, М. Шефер, Р. Pruim Hyper-полиномиальные иерархий и полиномиальная скачок Теоретическая информатика Том 262 (... 2001), стр. 241-256 cse.sc.edu/~fenner/papers/hyp.pdf ). Или, может быть, вы действительно хотите попросить естественный такой язык.

L

$L$

Джошуа Грохов

@ Джошуа: Спасибо за комментарий и ссылку. Как указано в обновлении (редакция 3), теперь я думаю, что задал правильный вопрос (вопреки тому, что я добавил в редакции 2). Я хотел знать: «Есть ли способ доказать условный результат« P = NP ⇒ L∈P », не доказав безусловный результат L∈PH?». Для этой цели естественность проблемы не должна требоваться, потому что когда-то Это метод доказательства, он должен применяться в равной степени как к естественным, так и к надуманным примерам.

Цуёси Ито

Ответы:

Поскольку вы не возражаете против искусственного языка, как насчет определения как пустого, если P равно NP, и как о проблеме остановки, если P не равно NP. Хорошо, это немного чит, но я думаю, что вам нужно перефразировать проблему, чтобы избежать таких читов. $L$

Рави Боппана
источник

Спасибо, я вижу смысл (определите L = {M: машина Тьюринга останавливается и P ≠ NP}). Конечно, это не отвечает на то, что я хотел спросить, но я думаю, что мне нужно больше думать, чтобы сформулировать вопрос, который я хотел задать правильно.

Цуёси Ито

Если искусственный пример действительно так же хорош, как и естественный, то я действительно могу привести такой пример!

Изменить: Кроме того, мой пример "несколько" менее обман, чем тот, который предложил Рави Боппана (где мы принимаем L в качестве пустого языка, если P = NP и проблема остановки в противном случае), в этом я буду определять язык L, дав конечную процедуру, чтобы решить, является ли L для любого входа x. Ни при каких условиях решение x∈L не требует решения «неограниченного» математического вопроса, такого как P против NP. $x \in$

Без лишних слов: пусть быть перечислением машин Polytime Тьюринга. Для всех пусть будет первым лексикографически который правильно решит 3SAT для всех входов длины или меньше. Затем определите язык L следующим образом: для всех входов размера , L тогда и только тогда, когда машина Тьюринга, закодированная с помощью останавливается не более чем на $M_1, M_2, ...$ $n$ $M_{t(n)}$ $M_i$ $n$ $x$ $n$ $x \in$ $x$ $n^{t(n)}$ шаги при запуске на пустой ленте.

Утверждение 1. Если P = NP, то L P. $\in$

Доказательство: если P = NP, то есть некоторая фиксированная которая решает 3SAT для всех входов; следовательно, для всех . QED $M_i$ $t(n) \le i$ $n$

Утверждение 2: если P NP, то L P. $\ne$ $\notin$

Доказательство: если возрастает без ограничения, то мы можем просто применить теорему иерархии времени. QED $t(n)$

Теперь, не только L не в P, предполагая P NP: можно предположить, что он не будет в PH (или даже в PSPACE)! $\ne$

Кстати, мне интересно, может ли кто-нибудь улучшить вышеуказанную конструкцию, чтобы получить язык L, который находится в P, если P = NP, но доказуемо не в PH или PSPACE, если P NP? $\ne$

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

Благодарность! Я не был в состоянии изменить конструкцию, чтобы сделать неучастие в доказуемости PH, но этого достаточно, чтобы убедить меня в том, что добавление условия, что L разрешима с конструктивным доказательством разрешимости, вряд ли изменит ситуацию. Хм.

Цуёси Ито

Я приму ответ Рави Боппаны, потому что он пришел первым, хотя я хочу принять оба, потому что оба дали мне больше понимания проблемы. Я надеюсь, что вы понимаете ...

Цуёси Ито

Ницца. Это отличный ответ.

Даниэль Апон

@ Тайсон Уильямс: на всякий случай, если вы не поняли, пожалуйста, будьте очень осторожны, чтобы не допустить ошибки при редактировании сообщения другими пользователями. К счастью, Джо заметил это и исправил.

Цуёси Ито

Отвечая на вопрос Ааронсон, но немного слишком долго для комментария, здесь является построение языка такая , что предполагает , но означает . $L$ $P = NP$ $L \in P$ $P \neq NP$ $L \notin PH$

Пусть и , как в конструкции Скотта. Мы сделаем так, чтобы не сводилось к для каждого , но мы делаем это только в том случае, если (т.е. если ). Строительство продолжается поэтапно. На этапе $M_1, M_2, M_3, \dotsc$ $t(n)$ $L$ $\Sigma_{k} SAT$ $k$ $t(n) \to \infty$ $P \neq NP$ $s=(i,j)$ ( с помощью легко вычислимым и легко обратимый биекция ), мы обеспечиваем что не много-один сокращения по сравнению с на . Пусть наименьшее целое число, такое что (базовый случай: ). Если существует такое целое число , то задайте $\Sigma^* \to \Sigma^* \times \Sigma^*$ $M_i$ $L$ $\Sigma_{j} SAT$ $n_{s}$ $t(n_{s}) > t(n_{s-1})$ $n_{0} = 1$ $n_{s}$ . Если такого целого числа , мы оставим пустым навсегда. $L(1^{n_{s}}) = 1 - \Sigma_{k}SAT(M_{i}(1^{n_{s}}))$ $n_{s}$ $L$

Если , то в , так что всегда есть такая , следовательно , не в . Если , то мой только конечно отличается от Скотта , и , следовательно , находится в . $P \neq NP$ $t(n) \to \infty$ $n \to \infty$ $n_{s}$ $L$ $PH$ $P = NP$ $L$ $L$ $P$

Джошуа Грохов
источник

Спасибо за ваш ответ, но я не уверен, что понимаю конструкцию. Мне кажется, что для вычисления

может потребоваться поиск в течение неопределенного времени, и поэтому мне кажется, что у нас нет явного алгоритма для определения языка L. Если нам не нужен явный алгоритм, ответ Рави Боппаны показывает, что существует такой язык L, что P = NP⇒L∈P и P ≠ NP⇒L∉R (т. е. L неразрешима).

n_{s}

$n_s$

Цуёси Ито

n_{s}

$n_s$

s

$s$

1^{n}

$1^n$

n

$n$

n_{s}

$n_s$

s

$s$

s

$s$

1^{n}

$1^n$

t (n)

$t(n)$

t (m)

$t(m)$

m < n

$m < n$

m < n

$m < n$

t (n) = t (m)

$t(n)=t(m)$

n

$n$

n_{s}

$n_s$

s

$s$

L (1^{n}) = 0

$L(1^n) = 0$

s

$s$

n_{s}

$n_s$

t

$t$

L (1^{n})

$L(1^n)$