A Paridade-P está contida no PP?

Jan Pax fez essa pergunta na lista de discussão Fundamentos da Matemática . Certamente mas suspeito pelas respostas desta pergunta que não se sabe se (caso contrário, o seria um possível resposta a essa pergunta). Se não se sabe, existe uma separação do oráculo? $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ $\oplus P \subseteq PP$ $PP$

cc.complexity-theory complexity-classes Timothy Chow
fonte

A Wikipedia diz que existe um oráculo para o qual ( R. Beigel, H. Buhrman e L. Fortnow. ser tão fácil como a detecção de soluções únicas )

P^{A} = \oplus P^{A} \neq N P^{A} (= P P^{A}) = E X P^{A}

$P^A = \oplus P^A \neq NP^A ( = PP^A) = EXP^A$

Marzio de Biasi

Obrigado, Marzio. Acho que deveria ter sido mais específico: existe um oráculo tal que ?

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

O que vou dizer é incluído nas outras respostas, mas pode ser útil se você quiser manter as coisas simples. O oráculo que você está procurando é apenas uma aplicação do fato conhecido de que um perceptron não pode computar PARITY (Minsky & Papert).

Alessandro Cosentino 24/03

@AlessandroCosentino

P P^{\oplus P} = P P

$PP^{\oplus P}=PP$ e

{\oplus P}^{P P} = P P

${\oplus P}^{PP}=PP$ ? E se

P P \subseteq \oplus P

$PP\subseteq\oplus P$ fosse verdadeiro?

T ....

Respostas:

Sim, há um oráculo $A$ tal que $\oplus P^A \not\subseteq PP^A$ . De fato, existe um oráculo $A$ tal que $\oplus P^A \not\subseteq PP^{PH^A}$ . Você pode encontrar o resultado no documento a seguir.

Frederic Green, Um oráculo que separa $\oplus P$ de $PP^{PH}$ , Information Processing Letters, Volume 37, Edição 3, 18 de fevereiro de 1991, páginas 149-153

Robin Kothari
fonte

Obrigado ... é exatamente isso que eu estava procurando! Nos comentários iniciais de seu trabalho, Green credita o doutorado de Jacobo Torán. tese com o primeiro a Oracle tal que . Esse resultado foi publicado posteriormente como o Teorema 5.13 no artigo de Torán "Classes de complexidade definidas por quantificadores de contagem", JACM 38 (1991), 752-773.

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

Scott Aaronson fornece um oráculo onde P = PEXP, o que implica o oráculo que você deseja. http://eccc.hpi-web.de/report/2005/040/download/ (Teorema 12 no apêndice) $\oplus$

Lance Fortnow
fonte

Obrigado. Eu tenho que escolher apenas uma resposta para aceitar, então eu estou escolhendo a resposta de Robin Kothari, porque é uma referência anterior.

Timothy Chow