¿Se sabe algo no trivial sobre los cocientes de las clases de complejidad?

Question

Esta pregunta es sólo para la diversión y esto es totalmente fuera de mi zona, así que es probable tonto; disculpas de antemano.

Por un "cociente", me refiero a lo siguiente: supongamos que se tienen dos clases de complejidad, $A \subseteq B$. El cociente $B/A$ constaría de las clases de equivalencia de los elementos de $B$ por la relación $b \sim b'$ si usted puede solucionar $b'$ con un programa de $A$ entrada de un oráculo para $b$, y vice-versa. (No sé si este concepto tiene un nombre o se llama de otra forma, lo siento.)

(Para dar el ejemplo obvio, el $P$ frente al $NP$ problema pregunta de si $NP/P$ es trivial.)

Puede algo interesante que decir acerca de este concepto?

Answer 1

Creo que es ampliamente estudiado en oracle máquinas de turing. Aquí está un ejemplo de este libro.

Vamos $EXPCOM$ = $\{<M,x,1^n>:$ M outpits 1 en $2^n$.$\}$

Ahora considere el $P^{EXPCOM}/EXP$ junto con su definición.

Claramente $EXP\subseteq P^{EXPCOM}$. Ahora para dos problema $(b,b')$ $P^{EXPCOM}$ y si existe un polinomio reducción del tiempo de $b\leq_P b'$, entonces se crea una clase de equivalencia desde un programa de $EXP$ (que acaba de hacer el polinomio de reducción de tiempo de consultas y el dado de oracle TM) puede resolver b'.