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

15

Мы все знаем, что у есть барьеры. Мы все изучили эти барьеры, потому что мы считаем, что .P N PPNPPNP

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

Т ....
источник
2
Как указывал Каве, если P = NP, то естественный барьер доказательств, похоже, исчезает. Барьеры релятивизации и алгебризации уже работали против и . Поэтому я думаю, что ответ таков: естественные доказательства, кажется, не применяются, но алгебризация и релятивизация все еще применимы. P N PP=NPPNP
Джошуа Грохов
3
@ThomasKlimpel: Релятивизация определенно относится к P = NP: Бейкер-Гилл-Соловей дал оракула, относящегося к P = NP, и оракула, относящегося к P NP, что означает, что методы релятивизации не могут разрешить вопрос P против NP в в любом направлении . Алгебризация была введена потому, что доказательство того, что IP = PSPACE (и связанные с ним вещи, такие как MIP = NEXP) не релятивизируется.
Джошуа Грохов
1
@JoshuaGrochow Что такое релятивизирующая техника для доказательства равенства? Использует ли доказательство того, что log (n) -AuxPDA равно P, используется метод релятивизации? Я полагаю, что где-то читал, что существует оракул, относительно которого log (n) -AuxPDA! = P, но, возможно, это больше связано с тонкостями оракулов для ограниченных в пространстве вычислений. Однако для доказательства неравенства довольно очевидно, что большинство известных методов релятивизируются.
Томас Климпел
1
@ThomasKlimpel: примером алгебраической техники для доказательства равенства является результат IP = PSPACE. Я считаю, что NL = coNL релятивизируется. Я уверен, что результат AUC-SPACE (poly) = PSPACE релятивизируется. На самом деле, мне трудно думать о любом результате равенства, который не релятивизируется и не алгебрирует. Re: «и если вы знаете этот алгоритм»: если P = NP, в некотором смысле мы делаем, а именно Левин универсальный поиск! Но Левин универсальный поиск релятивизирует ...
Джошуа Грохов
2
Нет никакого реального барьера для какого-то сумасшедшего алгоритма, который случается, чтобы решить булеву удовлетворенность. Отсутствие такого барьера, безусловно, не означает правды или даже вероятности.
Ланс Фортноу

Ответы:

8

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

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

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

Питер Шор
источник
1
Препринт Фиорини и соавт. is arxiv.org/abs/1111.0837v5
Андрас Саламон
1
Отношение последнего результата к P против NP обсуждается, например, здесь: cs.stackexchange.com/a/80173/1084
Мартин Шварц