Доказательства, барьеры и P против NP

25

Хорошо известно, что любое доказательство, решающее вопрос P против NP, должно преодолевать релятивизацию , естественные доказательства и барьеры алгебраизации . Следующая диаграмма разбивает «пространство доказательств» на различные области. Например, соответствует набору доказательств, которые релятивизируются и натурализуются. (теория геометрической сложности), конечно, строго за пределами региона. $RN$ $GCT$

Назовите некоторые доказательства вместе с самыми известными регионами, к которым они принадлежат. Разместите их наилучшим образом, т. Е. Если известно, что доказательство релятивизирует, натурализует и алгебрирует, то оно должно быть помещено в не только в . Если доказательство релятивизируется, но не натурализуется, оно принадлежит и т. Д. $RNA$ $RN$ $R$ ${\setminus}$ $N$

альтернативный текст

cc.complexity-theory proofs barriers p-vs-np Шива Кинтали
источник

Но есть ли какие-либо известные достоверные доказательства P против NP вообще?

gphilip

2

Я думаю, что это классический вопрос CW.

Суреш Венкат

@gphilip Речь идет о нижних оценках доказательства в теории сложности в целом.

Шива Кинтали

@Suresh Размещение доказательств в этих регионах очень нетривиально. Люди, публикующие ответы, должны быть вознаграждены (конечно же, повышением голосов) за их знание и понимание этих барьеров. Что вы думаете ?

Шива Кинтали

Прочитав приведенный ниже ответ Суреша, я думаю, что у меня возник вопрос (поправьте меня, если я ошибаюсь): вы ищете классификации вида «Если доказательство, которое разрешает P против NP, обладает свойством X, то оно принадлежит области Y в картина." В ответе Суреша X - «Интерактивный», а Y - вне R, возможно, также и вне N.

gphilip

17

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

Райан Уильямс
источник

Привет, Райан, я сохранил простую диаграмму, чтобы мы могли также обсудить «распад» этих регионов. Например, ваш ответ можно переформулировать как « в смысле Ааронсона-Вигдерсона».

R \subseteq A

$R \subseteq A$

Шива Кинтали

4

То, что говорит Райан, относится только к сдерживанию. Результат, подобный P = NP, подразумевает, что P = PH релятивизируется, но не алгебрирует.

Лэнс Фортноу

@Lance: Спасибо за разъяснения. Поэтому имеет смысл оставить диаграмму такой, какая она есть.

Шива Кинтали

3

Я только что видел это сейчас ... на самом деле, Скотт и Ави также дают несколько "алгебраических" последствий. Их понятие определено таким образом, чтобы включить релятивизацию. (Для импликации, которую приводит Ланс, они, вероятно, сказали бы, что алгебрирующая импликация - это " подразумевает . ")

P^{\tilde{A}} = N P^{\tilde{A}}

$P^{\tilde{A}} = NP^{\tilde{A}}$

P H^{A} \subseteq P^{\tilde{A}}

$PH^{A} \subseteq P^{\tilde{A}}$

Райан Уильямс

13

Вопреки некоторым утверждениям ранее в этой теме, алгебризация в смысле Aaronson & Wigderson не относится к релятивизации. Например,

\begin{matrix} (†) & (\exists C : C \subset N E X P \land C ⊄ P / p o l y) ⟹ N E X P ⊄ P / p o l y \end{matrix}

$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$

это утверждение, которое релятивизирует. (На самом деле у него есть релятивизирующее доказательство, что бы это ни значило для читателя.) Но это не известно, как алгебраизировать, на что ссылаются сами Ааронсон и Вигдерсон в Разделе 10.1 своей статьи [1]. (Следовательно, в то время как AW говорит нам, что в приведенной выше диаграмме должен лежать вне , возможно, что лежит внутри!) $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $\mathrm {A}$ $\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$

Однако недавняя работа Эрика Баха и меня [2] дает формулировку алгебризации, которая включает релятивизацию. По сути, если мы возьмем понятие AW алгебраического оракула, обозначенного как для некоторого языка и мудро изменим его, то мы сможем устранить патологии, такие как выше. $\tilde O$ $O$ $(\dagger)$

В результате алгебраизация, когда она определена надлежащим образом, является релятивизацией по отношению к алгебраическому оракулу - алгебраической релятивизацией, где каждый оракул получает «покачивание» - что означает - пустое множество на диаграмме выше, следовательно, . $\mathrm{R} \setminus \mathrm{A}$ $\mathrm{RN}$

[1] http://www.scottaaronson.com/papers/alg.pdf
[2] http://eccc.hpi-web.de/report/2016/040/

PS: еще одна формулировка для алгебризации была предложена Импальяццо, Кабанецом и Колоколовой ранее, которая также помещает в , но, как известно, не такой мощный, как понятие AW. Посмотрите мою статью с Эриком для сравнения. $\mathrm{R}$ $\mathrm{A}$

Барыш Айдынлыоглу
источник

Спасибо, Барис. Я рад, что кто-то наконец нашел понятие алгебризации, которое формально делает то, что мы думаем, что должно :)

Райан Уильямс

11

В теоремы времени и пространства иерархии релятивизировать. Они одинаковы, поэтому они не натурализуются.

Я думаю, что косвенные результаты диагонализации, такие как нижние границы пространства-времени Ланса Фортнау и соавт. а также результат Райана Уильямса не релятивизируется, потому что они не являются черным ящиком (но я не уверен в этом). Доказательства не кажутся естественными, так как они используют теоремы иерархии.

Доказательства перманента не в однородном $TC^0$ используют теоремы иерархии и, кажется, не работают для неоднородного случая, и, кажется, не натурализуются. С другой стороны, я не знаю, являются ли они релятивизированными, они могут с подходящим понятием релятивизации.

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

7

Интерактивные доказательства не релятивизируются. Я не думаю, что они натурализуются, поскольку они одинаковы.

Суреш Венкат
источник

Доказательства, барьеры и P против NP

Ответы: