Intuición detrás de la relativización

Question

Supo rumbo sobre la complejidad computacional. Mi problema es que no entiendo Método de relativización. Traté de encontrar un poco de intuición en muchos libros de texto, desafortunadamente, hasta ahora sin éxito. Agradeceré si alguien podría arrojar la luz sobre este tema para poder continuar solo. Pocas oraciones siguientes son preguntas y mis pensamientos sobre la relativización, ayudarán a navegar por la discusión.

Muy a menudo, la relativización viene en comparación 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 de que $ P $ versus $ np $ pregunta no se puede resolver mediante diagonalización. Realmente no veo la idea de por qué la relativización muestra el inútil de la diagonalización, y si es inútil, por qué es realmente inútil.

La idea detrás de Oracle Turing Machine $ m^a $ al principio es muy clara. Sin embargo, cuando se trata de $ np^a $ y $ p^a $, la intuición desaparece. Oracle es un Blackbox diseñado para un lenguaje especial y responde a la pregunta de si la cadena en la entrada del Oracle está en el idioma en el tiempo 1. Como entendí que contiene un Oracle, solo hace algunas operaciones auxiliares y pregunté al Oracle. Entonces, el núcleo del TM es el Oráculo, todo lo demás es menos importante. ¿Cuál es la diferencia entre $ p^a $ y $ np^a $, incluso pensó que Oracle en ambos trabaja en el tiempo 1?

Lo último es probar la existencia de un oráculo $ b $ tal que $ p^b neq np^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" por Sipser, Capítulo9. Dificultad, y no tuvo la idea de la construcción de una lista de todo el tiempo polinomial oracle tms $ m_i $.

Esto es más o menos todo lo que sé sobre la relativización, apreciaré si Someonw decidiría compartir sus pensamientos sobre el tema.

Apéndice: En uno de los libros de texto encontré un ejemplo de $ np^b $ lenguaje (complejidad computacional: un enfoque moderno de Boaz Barak Sanjeev Arora. Teorema 3.7. Página 74). $ U_b = left {1^n: algunos Space String Space of Space Longitud Space n Space IS Space in Space B Right } $ Es un lenguaje unario. Creo que (1,11,111,1111, ...) están en $ U_B $. El autor afirma que dicho lenguaje está en $ np^b $, que 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 un buen ejemplo de $ np^b $, ponga el suyo tal que para aprobar la existencia de $ np^b $.

Answer 1

Realmente no ha hecho ninguna pregunta, pero parece que no sabe qué significa $ rm {p}^a $ y qué $ rm {np}^a $ significa para un idioma $ a $. La clase $ rm {np}^a $ es simplemente todos los idiomas que son decidibles en "Tiempo NP", dada una máquina Turing con $ A $ como Oracle. Esto significa una máquina Turing no determinista con acceso a $ A $ que se ejecuta en tiempo polinomial. El $ rm {p}^a $ es la versión determinista.