Clases de complejidad potencialmente iguales sin relativizaciones contradictorias conocidas

¿Cuáles son algunos ejemplos de pares de clases de complejidad y tales que $A$ $B$

no sabemos si , y $A=B$
tampoco conocemos relativizaciones contradictorias (es decir, no conocemos los oráculos y manera que y )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Para formular la pregunta de otra manera, ¿cuáles son algunas excepciones a la heurística de que si no se pueden resolver relativizaciones contradictorias, entonces es fácil resolver la cuestión de la igualdad directamente?

cc.complexity-theory complexity-classes relativization Timothy Chow
fuente

¿Serían suficientes dos clases A y B para las cuales no sabemos cómo demostrar una separación de oráculo entre A y B para responder a su pregunta? (Suponiendo que sea posible que A y B sean iguales.)

Robin Kothari

¿Aceptaría ejemplos sobre las implicaciones entre las igualdades, en lugar de las igualdades individuales? Por ejemplo, no sabemos si NP = UP implica que el PH colapsa, pero tampoco tenemos un oráculo en el que esta implicación sea falsa.

Joshua Grochow

@JoshuaGrochow: Eso es interesante, aunque estoy un poco más interesado en el tipo específico de ejemplo que describí.

Timothy Chow

@Robin Kothari: Si no conocemos un oráculo Q, a fortiori no conocemos los oráculos P y Q, por lo que la única forma en que veo (A, B) para satisfacer sus requisitos pero no los míos es si sabemos que A = B pero no conocemos un oráculo que los separe. Supongo que puede ser interesante ver un ejemplo de A y B de tal manera que A = B, pero es plausible (pero no se sabe) que podrían estar separados por un oráculo, pero esto no es realmente lo que estaba pidiendo.

Timothy Chow

Respuestas:

Creo que el mayor ejemplo de este tipo en la actualidad es (tiempo polibomial cuántico) frente a (la jerarquía de tiempo polinomial). Se ha realizado un esfuerzo significativo para separarlos en relación con un oráculo, sin éxito. (Por supuesto, un oráculo lo suficientemente poderoso los hará iguales). Y el resultado de contención más conocido es que está en $BQP$ $PH$ $BQP$ . $PP$

Algunas referencias para ataques al problema del oráculo: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

Ryan Williams
fuente

En realidad el mejor resultado conocido es

, donde

es (entre otras cosas) la más grande sublcass GAP-definible de

tal que

. No conozco ningún interés en la clase

aparte de su relación con

y con

B Q P \subseteq A W P P \subseteq P P

$\mathsf{BQP \subseteq AWPP \subseteq PP}$

A W P P

$\mathsf{AWPP}$

P P

$\mathsf{PP}$

P P^{A W P P} = P P

$\mathsf{PP^{AWPP} = PP}$

A W P P

$\mathsf{AWPP}$

B Q P

$\mathsf{BQP}$

P P

$\mathsf{PP}$ , por lo que, como refinamiento, este es un punto un poco técnico, pero ahí lo tienes.

Niel de Beaudrap

En este sentido, tampoco se sabe cómo separar BQP de AM, o incluso QMA de AM.

Robin Kothari

¿Hay algún oráculo que separe de ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

Ryan O'Donnell
fuente

Estoy bastante seguro de que la pregunta tenía una intención más retórica, es decir, "Creo que esta es una respuesta, pero tal vez hay un oráculo conocido que no conozco"

Joshua Grochow

Si, gracias Josh. ¿Conoces uno? Es muy difícil de buscar, pero recuerdo no haber podido conocer la existencia la última vez que lo intenté.

Ryan O'Donnell