Intuición detrás de la relativización

Tomo curso sobre Complejidad Computacional. Mi problema es que no entiendo el método de relativización . Intenté encontrar un poco de intuición en muchos libros de texto, desafortunadamente, hasta ahora sin éxito. Apreciaré si alguien pudiera arrojar luz sobre este tema para poder continuar por mí mismo. Pocas oraciones siguientes son preguntas y mis pensamientos sobre la relativización ayudarán a navegar la discusión.

Muy a menudo, la relativización se compara con la diagonalización, que es un método que ayuda a distinguir entre un conjunto contable y un conjunto incontable. De alguna manera proviene de la relativización que la pregunta versus N P no puede resolverse mediante la diagonalización. Realmente no veo la idea de por qué la relativización muestra lo inútil de la diagonalización, y si es inútil, por qué es realmente inútil.$P$$NP$

La idea detrás de la máquina Oracle Turing al principio es muy clara. Sin embargo, cuando se trata de N P A y P A, la intuición desaparece. Oracle es una caja negra que está diseñada para un lenguaje especial y responde a la pregunta de si la cadena en la entrada del oráculo está en el idioma en el tiempo 1. Como entendí TM que contiene un oráculo es solo hacer algunas operaciones auxiliares y preguntarle al oráculo. Entonces, el núcleo de la TM es el oráculo, todo lo demás es menos importante. ¿Cuál es la diferencia entre P A y N P A , incluso si el oráculo en ambos funciona en el tiempo 1?$M^A$$NP^A$$P^A$$P^A$$NP^A$

Lo último es la prueba de la existencia de un oráculo tal que P B ≠ N P B . Encontré la prueba en varios libros de texto y en todos ellos la prueba parece muy vaga. Traté de usar "Introducción a la complejidad" de Sipser, Capítulo 9. Intractabilidad , y no se me ocurrió la idea de construir una lista de todas las TM de oráculo de tiempo polinomial M i .$B$$P^B \neq NP^B$$M_i$

Esto es más o menos todo lo que sé sobre relativización, agradeceré si alguien decide compartir sus pensamientos sobre el tema.

Anexo : en uno de los libros de texto encontré ejemplos de lenguaje (Complejidad computacional: un enfoque moderno de Boaz Barak Sanjeev Arora. Teorema 3.7. Página 74). U B = { 1 n : s o m e s t r i n g o f l e n g t h n i s i n B } es un lenguaje unario. Creo que (1,11,111,1111, ...) están todos en T B . El autor afirma que tal lenguaje está en$NP^B$$U_B=\left \{ 1^n:some \space string \space of \space length \space n \space is \space in \space B\right \}$$U_B$ que es, no puedo entender por qué, por lo tanto, Oracle para B puede resolver todo a tiempo 1. ¿Por qué necesitamos TM no determinista con Oracle? Si no es buen ejemplo de N P B Por favor, ponga el suyo de tal manera que para aprobar la existencia de N P B .$NP^B$$NP^B$$NP^B$

Realmente no se ha solicitado ninguna pregunta, pero parece que no se sabe qué significa y lo N P A través de un lenguaje A . La clase N P A es simplemente todos los idiomas que son decidibles en "tiempo NP", dada una máquina de Turing con A como oráculo. Esto significa una máquina de Turing no determinista con acceso a A que se ejecuta en tiempo polinómico. El P A es la versión determinista.$\rm{P}^A$$\rm{NP}^A$$A$$\rm{NP}^A$$A$$A$$\rm{P}^A$