¿Son los oráculos asociativos?

Esta pregunta puede tener una respuesta obvia ... pero aquí está la pregunta de todos modos. Intuitivamente, es la siguiente declaración plausible: "una máquina con una subrutina A que a su vez tiene una subrutina B es lo mismo que una máquina con una subrutina A que tiene acceso a la subrutina B".

Para definir este problema formalmente, usaré alguna notación no convencional. Cuando digo , le doy a A un oráculo por un problema B - C o m p l e t e . por ejemplo, N P N P = N P S A T = Σ 2 . Con esta "nueva" notación, es posible definir A B C , y así sucesivamente. Mi pregunta es, es$A^B$$A$$B-Complete$$NP^{NP}=NP^{SAT}=\Sigma_2$$A^{B^C}$

• ¿Es esta una forma válida de pensar acerca de los oráculos?
• es $(A^B)^C = A^{(B^C)}$

Por ejemplo, $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$

No puedo pensar en contraejemplos obvios de esta regla. ¿Nadie?

Como Venkat dijo en los comentarios, parece difícil entender su definición de oráculo que no se define como alguna caracterización de la máquina.

Sea el conjunto de TM en A con un oráculo que es una máquina en ( B con un oráculo en una máquina en C ). Es obvio que una máquina en A puede llamar a C : que sólo llama a la máquina en B y le pide que llevar el mensaje directamente al C .$A^{(B^C)}$$A$$B$$C$$A$$C$$B$$C$

Supongo que sería una máquina en A que puede llamar a un oráculo en C o un oráculo que es (una máquina en B que puede llamar a una máquina en C ), por lo que es exactamente la misma definición.${(A^B)}^C$$A$$C$$B$$C$

$A^{B,C}$$B=C=NP$$A=P$$A^{B,C}=NP\cup coNP$$A^{(B^C)}=\Sigma_2^P\cup\Pi_2^p$

Escribiría lo siguiente como comentario, pero fue demasiado largo para encajar.

$\bf C$

$\bf{LOGSPACE}^A$$A \in \bf{LOGSPACE}^A$ se mantiene con probabilidad 1 para [LL] pero no para [Si])

[LL] RE LADNER Y NA LYNCH, Relativización de preguntas sobre computabilidad del espacio logarítmico , Matemáticas. Teoría de sistemas, 10 (1976), pp. 19-32.

[Si] J. SIMON, Sobre algunos problemas centrales en la complejidad computacional , Tech. Representante TR 75-224, Departamento de Informática, Universidad de Cornell, Ithaca, NY, 1975.

$X = B^C$$X = \bigcup_{L\in C}{B^L}$$B^L$

$A^X = A^{(B^C)}$$X^A = (B^C)^A$

• $A^X$$L' \in X = \bigcup_{L\in C}{B^L}$$A ^ X = \bigcup\limits_{L'\in \{\bigcup\limits_{L\in C}{B^L}\}}{A^{L'}}$

• $X^A$$X = \bigcup_{L\in C}{B^L}$$L' \in A$$X ^ A = \bigcup_{L' \in A} {{X^{L'}}} = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}}$

$(B^{L_1})^{L'} \cup (B^{L_2})^{L'} = (B^{L'})^{L_1 \cup L_2}$

Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.

$X ^ A = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}} = \bigcup_{L \in C, L' \in A} {{{\left( B^{L'} \right)}^L}}$

Ejemplo

$\bf X = \bf{P^{NP}}$$\bf{coNP} \subseteq \bf X$$\bf {NP}$$\bf{coNP^{NP}} \subseteq \bf{X^{NP}} = (\bf{P^{NP}})^{\bf{NP}}$

Epílogo

Una fructífera discusión con Tsuyoshi Ito reveló (para mí) que no es fácil relativizar doblemente una clase de complejidad. De hecho, incluso definir uno parece ser problemático. Definitivamente debería estudiar más para ver si alguna vez se da alguna definición satisfactoria. Mientras tanto, agradezco cualquier comentario que pueda usarse para resolver este problema.