É

Por http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

Se é uma linguagem PSPACE-completo, . $A$ $P^{A}=NP^{A}$

Se é um oráculo determinístico de tempo polinomial, (assumindo ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

é a classe de problemas de decisão analógica para e , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

mas nem nem são conhecidos. Mas é verdade que $P=PP$ $PP=PSAPCE$

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

cc.complexity-theory complexity-classes counting-complexity open-problem oracles Mike Chen
fonte

é um oráculo de tempo polinomial determinista, eu acho que você quer dizer que acreditam

. (desde

)

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$

Ramprasad

Posso estar errado, mas deixe-me tentar: Sua primeira pergunta assume que a segunda contenção não é rigorosa. Em outras palavras, assume que PP = PSPACE. Nesse caso, acho que a igualdade se aplica ao resultado que você mencionou no início. Estou certo? (PS: O inverso vale para a 2ª pergunta.)

MS Dousti 30/10/10

O Teorema de Toda pode ser relevante aqui, pois indica que alguém pode dobrar a diferença entre

no oráculo

. (Mas eu não estou 100% certo sobre isso.)

P

$P$

N P

$NP$

#P

$#P$

Boaz Barak

A resposta para sua quarta pergunta é sim. Até NP ^ PSPACE está contido no PSPACE; portanto, o NP com um oracle #P está no PSPACE.

Robin Kothari

Como sugerem os comentários, algumas das perguntas mencionadas nesta postagem (e algumas das perguntas que você adicionou recentemente) são básicas. Por favor, mostre alguma evidência de que você realmente se importa. Consulte também meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Tsuyoshi Ito

Respostas:

É um problema aberto na teoria da complexidade por muitos anos se entrar em colapso, onde é a hierarquia polinomial do tempo. É também um problema em aberto para a construção de uma técnica para separar de . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Bin Fu
fonte

Bem-vindo ao CSTheory.SE, @Bin Fu! :)

Daniel Apon

Ou talvez você já esteve aqui antes, mas seja bem-vindo de qualquer maneira! ;)

Daniel Apon

Obrigado, Daniel Apon. Sabe-se que PH ^ {Parity P} entra em colapso. Será muito interessante se pudermos provar que o PH ^ {# P} entra em colapso.

Bin Fu

P H^{# P}

$PH^{\#P}$

Por 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}$

Mike Chen
fonte

A inclusão P ^ X P NP ^ X ∩ coNP ^ X para qualquer classe X é clara a partir da definição, e você não precisa do Teorema 4.1 de Torán para isso. Não vejo por que os colapsos da hierarquia polinomial e da hierarquia de contagem implicam P ^ # P = NP ^ # P = coNP ^ # P. Você pode elaborar?

Tsuyoshi Ito

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$

=

$=$

“A hierarquia polinomial entra em colapso” não significa necessariamente P = NP e “a hierarquia de contagem entra em colapso” não significa necessariamente PP = PP ^ PP.

Tsuyoshi Ito

Além disso, P = NP não implica P ^ # P = NP ^ # P, tanto quanto eu sei (mas posso estar faltando alguma coisa).

Tsuyoshi Ito

Um erro comum nesse tipo de argumento é assumir que a relativização para um oráculo é uma operação na coleção de linguagens, mas, em vez disso, é uma operação no tipo de computação, que afeta drasticamente quais linguagens estão na classe.

Derrick Stolee