Барьеры для отображения

Мы все знаем, что у есть барьеры. Мы все изучили эти барьеры, потому что мы считаем, что . $P\ne NP$ $P\ne NP$

Однако предположим, что и есть мудрые люди, которые считают, что такая возможность существует . Если это действительно так, то сам факт того, что мы не видели хороших алгоритмов, указывает на то, что в этой альтернативной вселенной могут быть и барьеры. Обеспечиваемость является барьером, и мы не знаем наверняка, что - это правда. Мы не знаем наверняка, что является правдой, и поэтому доказуемость также является барьером? $P=NP$ $P\ne NP$ $P\ne NP$ $P= NP$ $P=NP$

p-vs-np barriers Т ....
источник

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

P = N P

$P=NP$

P \neq N P

$P\neq NP$

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

@ThomasKlimpel: Релятивизация определенно относится к P = NP: Бейкер-Гилл-Соловей дал оракула, относящегося к P = NP, и оракула, относящегося к P NP, что означает, что методы релятивизации не могут разрешить вопрос P против NP в в любом направлении . Алгебризация была введена потому, что доказательство того, что IP = PSPACE (и связанные с ним вещи, такие как MIP = NEXP) не релятивизируется.

\neq

$\neq$

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

@JoshuaGrochow Что такое релятивизирующая техника для доказательства равенства? Использует ли доказательство того, что log (n) -AuxPDA равно P, используется метод релятивизации? Я полагаю, что где-то читал, что существует оракул, относительно которого log (n) -AuxPDA! = P, но, возможно, это больше связано с тонкостями оракулов для ограниченных в пространстве вычислений. Однако для доказательства неравенства довольно очевидно, что большинство известных методов релятивизируются.

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

@ThomasKlimpel: примером алгебраической техники для доказательства равенства является результат IP = PSPACE. Я считаю, что NL = coNL релятивизируется. Я уверен, что результат AUC-SPACE (poly) = PSPACE релятивизируется. На самом деле, мне трудно думать о любом результате равенства, который не релятивизируется и не алгебрирует. Re: «и если вы знаете этот алгоритм»: если P = NP, в некотором смысле мы делаем, а именно Левин универсальный поиск! Но Левин универсальный поиск релятивизирует ...

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

Нет никакого реального барьера для какого-то сумасшедшего алгоритма, который случается, чтобы решить булеву удовлетворенность. Отсутствие такого барьера, безусловно, не означает правды или даже вероятности.

Ланс Фортноу

Михалис Яннакакис показал, что задача коммивояжера не может быть решена за полиномиальное время с помощью симметричной линейной программы.

См. Статью « Выражение задач комбинаторной оптимизации с помощью линейных программ » Яннакакиса.

Этот результат был недавно улучшен Фиорини, Массаром, Покуттой, Тивари и Де Вольфом, чтобы отбросить «симметричное» требование в результатах Яннакакиса.

Питер Шор
источник

Препринт Фиорини и соавт. is arxiv.org/abs/1111.0837v5

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

Отношение последнего результата к P против NP обсуждается, например, здесь: cs.stackexchange.com/a/80173/1084

Мартин Шварц

Барьеры для отображения

Ответы: