как оракул

12

Имеет ли NPNPcoNP=NPудерживать?

Ясно, что NPNPNP , но мне кажется, что NPcoNP является «детерминированным», что заставляет меня верить, что это правда.

Есть ли простое доказательство (или, может быть, просто по определению)?

Maomao
источник
6
Во-первых, да. Действительно, оракул A удовлетворяет условию NPA=NP тогда и только тогда , когда ANPcoNP . Этот класс называется Low(NP) или иногда L1P : сложностьzoo.uwaterloo.ca/ Complexity_Zoo : L# lkp . Во-вторых, я не думаю, что вообще ясно, что NPNPNP , хотя это широко распространенное мнение. В частности, это подразумевает PNP и, по-видимому, строго сильнее, так как в противном случае нет релятивизируемого следствия.
Джошуа Грохов
2
Кроме того, люди, которые считают, что ФАКТОРИНГ труден, могут не согласиться с вашей интуицией о том, что NPcoNP является «детерминистическим».
Ниль де Бодрап,
9
@JoshuaGrochow: я думаю, что вы должны добавить это как ответ, с некоторым изложением того, каковы классы в низкой иерархии; это примерно такой же хороший ответ, какой может получить ОП.
Ниль де Боудрап
2
содержит C O - N P , таквозможнообъясняетпочему он вряд ли будет равна N P . NPNPcoNPNP
domotorp
4
@NieldeBeaudrap: моя неуверенность в том, чтобы публиковать его как ответ, а не как комментарий, заключалась в том, что, хотя я полагаю, что maomao искренне задал этот вопрос всерьез, он может быть и был в прошлом, задан как домашнее задание.
Джошуа Грохов

Ответы:

13

Да. Действительно, оракул удовлетворяет условию Н Р А = Н P тогда и только тогда , когда A N P П с õ N P . Этот класс называется L o w ( N P ) или иногда L 1 P (см. Ссылку и цитируемую там статью для более подробного объяснения низкой иерархии в целом).ANPA=NPANPcoNPLow(NP)L1P

Ваша интуиция о «детерминизме» на самом деле несколько верна (хотя она не является достаточно детерминированной, чтобы мы могли сделать вывод, что ). Попробуйте выполнить это упражнение , и вы увидите , что это интуиция доказанной: первое шоу - тщательно, изложив деталь - что если P , то N P = N P . Выясните, какая именно часть вашего доказательства не работает, если вы только предполагаете, что A N P , а затем понимаете, почему эта часть работает, когда A N Pc oP=NPcoNPAPNPA=NPANP .ANPcoNP

(Показывать обратное тоже не сложно: означает A N Pc o N P. )NPA=NPANPcoNP

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