Relativizaciones de la Pregunta P =? NP

Investigamos versiones relativizadas de la pregunta abierta de si cada lenguaje aceptado de manera no determinista en tiempo polinomial puede ser reconocido de manera determinista en tiempo polinomial. Para cualquier conjunto X, sea PX (resp. NPX) la clase de lenguajes aceptados en tiempo polinomial por máquinas de consulta determinísticas (resp. no determinísticas) con oráculo X. Construimos un conjunto recursivo A tal que PA = NPA. Por otro lado, construimos un conjunto recursivo B tal que PB NPB. Se construyen oráculos X para realizar todas las relaciones de inclusión de conjuntos consistentes entre las clases relativizadas PX, NPX y co NPX, la familia de complementos de lenguajes en NPX. Se describen varios problemas abiertos relacionados.