Консенсус по P = NP в мире, где RP = NP

12

широко предположительно, чтобы быть ложным.RP=NP

Но представьте на мгновение, что это правда. В таком случае, насколько вероятно, что ?P=NP

Другими словами: в мире, где , что еще может помешать нам верить P = N P ?RP=NPP=NP

cc.complexity-theory complexity-classes conditional-results Джорджио Камерани
источник
3
Другими словами, вы просите оракула, относительно которого RP = NP, но P NP. ≠
Юваль Фильмус
Да. Я хотел бы знать , является ли, в мире , где , дополнительные условия , которые должны быть верно для P ≠ N P являются более жесткими , и маловероятно , чем дополнительные условия , которые должны быть справедливо для P = N P . RP=NPP≠NPP=NP
Джорджио Камерани
7
@Yuval Filmus: Я не знаю, касается ли вопрос о барьере релятивизации, но если это так, то есть оракул, относительно которого RP = EXP (что подразумевает P ≠ RP = NP). Я не могу найти ссылку на этот факт сейчас, но это указано в замечании после теоремы 6 в Heller 1986 со ссылками на две статьи Курца и Хеллера, обе в трудах «Конференции по вычислительной теории сложности» в марте 1983 года.
Цуёси Ито

Ответы:

14

Честно говоря, я не думаю, что Stack Exchange - подходящее место, чтобы просить о будущем прогнозе. Несмотря на это, я опубликую ответ, потому что играть с идеей гадания интересно.

Насколько я знаю, возможность P ≠ RP = NP не исключена. Кроме того, существует язык таким образом, что РП = EXP [Hel83, Kur83], который сразу следует , что Р ≠ RP = NP . (Я не проверял [Hel83] или [Kur83], и я взял результат и ссылки из замечания после теоремы 6 в [Hel86].) Другими словами, даже доказательство импликации RP = NP ⇒ P = NP требует нерелятивизирующая техника, и поэтому понятно, что это не доказано.

(Ланс Фортнау обсуждает аналогичный результат в блоге «Вычислительная сложность: результаты Oracle хороши для вас» .)

Теперь давайте обратимся к гаданию.

Насколько этот результат оракула говорит о вероятности P = NP в мире, где RP = NP уже доказано? Немного. По крайней мере, это не должно восприниматься как доказательство того, что в мире, где RP = NP доказано, все еще трудно доказать P = NP. В таком мире некоторые новые, мощные нерелятивизирующие методы известны человеку, и поэтому было бы неразумно интерпретировать «требует нерелятивизирующую технику» как доказательство трудностей.

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

Ссылки

[Hel83] Ханс Хеллер. О релятивизированных полиномиальных иерархиях, распространяющихся на два уровня. В материалах конференции по вычислительной теории сложности , с. 109–114, Калифорнийский университет в Санта-Барбаре, март 1983 года.

[Hel86] Ханс Хеллер. О релятивизированных классах экспоненциальной и вероятностной сложности. Information and Control , 71 (3): 231–243, декабрь 1986 года. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] С. Курц (Стюарт А. Курц?). Тонкая структура НП: Релятивизации. В материалах конференции по вычислительной теории сложности , стр. 42–50, Калифорнийский университет в Санта-Барбаре, март 1983 года.

Цуёси Ито
источник
«Очевидно, что мы не можем применить нашу нынешнюю интуицию к рассуждениям о мире, где наша нынешняя интуиция впечатляюще терпит неудачу» ... это большое утверждение.
T ....