Является ли

Автор: http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf.

Если является PSPACE-полный язык, . $A$ $P^{A}=NP^{A}$

Если является детерминированным оракулом полиномиального времени, (при условии, что ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

- класс решений аналогичных задач для и , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

но ни ни не известны. Но правда ли, что $P=PP$ $PP=PSAPCE$

? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

cc.complexity-theory complexity-classes counting-complexity open-problem oracles Майк Чен
источник

Если

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

. (так как

)

B

$B$

P^{B} \neq N P^{B}

$P^B \neq NP^B$

P^{B} = P

$P^B = P$

N P^{B} = N P

$NP^B = NP$

Рампрасад

Я могу ошибаться, но позвольте мне попробовать: Ваш первый вопрос предполагает, что второе сдерживание не является строгим. Другими словами, предполагается, что PP = PSPACE. В этом случае, я думаю, равенство имеет место в результате, который вы упомянули в начале. Я прав? (PS: обратное верно для 2-го вопроса.)

MS Dousti 30.10.10

Теорема Тоды может быть уместна здесь, поскольку она указывает, что можно было бы свести разницу между

к оракулу

. (Но я не уверен на 100% в этом.)

P

$P$

N P

$NP$

#P

$#P$

Боаз Барак

Ответ на ваш четвертый вопрос - да. Даже NP ^ PSPACE содержится в PSPACE, поэтому, конечно, NP с оракулом #P находится в PSPACE.

Робин Котари

Как следует из комментариев, некоторые из вопросов, изложенных в этом посте (и некоторые из недавно добавленных вами вопросов), являются основными. Пожалуйста, покажите доказательства того, что вы действительно заботитесь. См. Также meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Цуёси Ито

Ответы:

В течение многих лет это является открытой проблемой в теории сложности, если разрушается, где - полиномиальная иерархия времени. Он также является открытой проблемой для построения оракула для разделения от . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Бин фу
источник

Добро пожаловать в CSTheory.SE, @Bin Fu! :)

Даниэль Апон

Или, может быть, вы были здесь раньше, но все равно добро пожаловать! ;)

Даниэль Апон

Спасибо, Даниэль Апон. Известно, что PH ^ {Parity P} разрушается. Будет очень интересно, если кто-нибудь докажет, что PH ^ {# P} рухнет.

Бин Фу

P H^{# P}

$PH^{\#P}$

Автор: http://portal.acm.org/citation.cfm?id=116858

$NP^{\mathbf{C}K}=\exists \mathbf{C}K$ $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$

$K$ $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$

$K$ $P$ $PP\subseteq\exists PP\cap\forall PP$

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

$P^{\#P}=NP^{\#P}=coNP^{\#P}$

Майк Чен
источник

Включение P ^ X ⊆ NP ^ X ∩ coNP ^ X для любого класса X ясно из определения, и для этого вам не нужна теорема 4.1 Торана. Я не могу понять, почему коллапсы полиномиальной иерархии и счетной иерархии подразумевают P ^ # P = NP ^ # P = coNP ^ # P. Можете ли вы уточнить?

Цуёси Ито

P = N P = c o N P

$P=NP=coNP$

P^{# P} = N P^{# P} = c o N P^{# P}

$P^{\#P}=NP^{\#P}=coNP^{\#P}$

C C P = C P

$\mathbf{C}\mathbf{C}P=\mathbf{C}P$

P P^{P P} = P P

$PP^{PP}=PP$

\exists K \cup \forall K \subseteq C K

$\exists K\cup\forall K\subseteq\mathbf{C}K$

P^{# P} \subseteq N P^{# P} \cap c o N P^{# P}

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

\subseteq N P^{# P} \cup c o N P^{# P} \subseteq P P^{P P}

$\subseteq NP^{\#P}\cup coNP^{\#P}\subseteq PP^{PP}$

= P P = P^{# P}

$=PP=P^{\#P}$

\subseteq

$\subseteq$

=

$=$

«Коллапсы полиномиальной иерархии» не обязательно означают P = NP, а «коллапсы иерархии счетчиков» не обязательно означают PP = PP ^ PP.

Цуёси Ито

Кроме того, насколько я знаю, P = NP не подразумевает P ^ # P = NP ^ # P (но я могу что-то упустить).

Tsuyoshi Ito

Распространенной ошибкой в аргументах такого типа является предположение, что релятивизация к оракулу - это операция над коллекцией языков, но вместо этого это операция над типом вычислений, которая существенно влияет на то, какие языки в классе.

Деррик Столи