¿Parity-P está contenido en PP?

Jan Pax hizo esta pregunta en la lista de correo de Fundamentos de Matemáticas . Ciertamente, $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ pero sospecho por las respuestas a esta pregunta que no se sabe si $\oplus P \subseteq PP$ (de lo contrario, $PP$ sería una posible respuesta a esa pregunta). Si no se sabe, ¿hay una separación de oráculo?

cc.complexity-theory complexity-classes Timothy Chow
fuente

Wikipedia dice que hay un oráculo para el cual

( R. Beigel, H. Buhrman y L. Fortnow. NP podría no ser tan fácil como detectar soluciones ú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

Gracias Marzio. Supongo que debería haber sido más específico: ¿Hay un oráculo

tal que

A

$A$

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

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

Timothy Chow

Lo que voy a decir está incluido en las otras respuestas, pero puede ser útil si quieres simplificar las cosas. El oráculo que está buscando es solo una aplicación del hecho conocido de que un perceptrón no puede calcular la PARIDAD (Minsky & Papert).

Alessandro Cosentino

@AlessandroCosentino ¿

? ¿Qué pasaría si

fuera cierto?

P P^{\oplus P} = P P

$PP^{\oplus P}=PP$

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

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

P P \subseteq \oplus P

$PP\subseteq\oplus P$

T ....

Respuestas:

Sí, hay un oráculo tal que . De hecho, no es un oráculo tal que . Puede encontrar el resultado en el siguiente documento. $A$ $\oplus P^A \not\subseteq PP^A$ $A$ $\oplus P^A \not\subseteq PP^{PH^A}$

Frederic Green, Un oráculo que separa de , Cartas de procesamiento de información, Volumen 37, Número 3, 18 de febrero de 1991, Páginas 149-153 $\oplus P$ $PP^{PH}$

Robin Kothari
fuente

Gracias ... ¡esto es exactamente lo que estaba buscando! En los comentarios de apertura a su artículo, Green acredita el Ph.D. de Jacobo Torán. tesis con la primera oráculo

tal que

. Este resultado se publicó posteriormente como Teorema 5.13 en el artículo de Torán "Clases de complejidad definidas por cuantificadores contadores", JACM 38 (1991), 752-773.

A

$A$

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

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

Timothy Chow

Scott Aaronson da un oráculo donde P = PEXP que implica el oráculo que deseas. http://eccc.hpi-web.de/report/2005/040/download/ (Teorema 12 en el apéndice) $\oplus$

Lance Fortnow
fuente

Gracias. Tengo que elegir solo una respuesta para aceptar, así que estoy eligiendo la respuesta de Robin Kothari porque es una referencia anterior.

Timothy Chow