Bajo (complejidad)

En la teoría de la complejidad computacional, se dice que una clase B de la complejidad es baja para una clase A de la complejidad si un = A; es decir un con un oráculo para B es igual a A. Tal declaración implica que una máquina abstracta que soluciona problemas en A no consigue ningún poder adicional si le dan la capacidad de solucionar problemas en B en el coste unitario. En particular, esto significa que si B es bajo para un entonces el B se contiene en A. Informalmente, bajo significa que los problemas en B sólo no son solubles por máquinas que pueden solucionar problemas en A, pero son "fáciles a solucionar." Una máquina puede simular muchas preguntas del oráculo a B sin exceder sus límites del recurso.

Los resultados y las relaciones que establecen una clase como baja para el otro a menudo se llaman resultados bajos.

Resultados

Se conoce que varias clases de la complejidad naturales son bajas para sí. Por ejemplo, el P es bajo para sí porque los algoritmos del tiempo polinomio se cierran bajo la composición. Informalmente, esto es verdad porque un algoritmo del tiempo polinomio puede hacer polinomiamente muchas preguntas a otros algoritmos del tiempo polinomio, reteniendo su duración polinomia. PSPACE también es bajo para sí, y esto puede ser establecido por exactamente el mismo argumento. Del mismo modo, el L es bajo para sí porque puede simular preguntas del oráculo del espacio del tronco en el espacio del tronco, reutilizando el mismo espacio para cada pregunta.

BPP también es bajo para sí y los mismos argumentos casi trabajan para BPP, pero uno tiene que explicar errores, haciendo ligeramente más difícil mostrar que BPP es bajo para sí. Del mismo modo, el argumento para BPP casi pasa para BQP, pero tenemos que mostrar además que las preguntas cuánticas se pueden realizar en la superposición coherente.

Cada clase que es baja para sí se cierra bajo el complemento. Esto es porque puede solucionar un problema de complemento preguntándose simplemente y luego invirtiendo la respuesta. Esto implica que NP no es bajo para sí a menos que NP = co-NP, que se considera improbable porque implica que la jerarquía polinomia cae al primer nivel, mientras que se cree extensamente que la jerarquía es infinita. El opuesto a esta declaración no es verdad. Si una clase se cierra bajo el complemento, no significa que la clase es baja para sí. Un ejemplo de tal clase es EXP, que se cierra bajo el complemento, pero no es bajo para sí.

Algunos resultados más complejos y famosos en cuanto a bajas de clases incluyen:

Aplicaciones

Bajo es particularmente valioso en argumentos relativization, donde puede ser usado para establecer que el poder de una clase no cambia del "relativized universo" donde una máquina del oráculo particular está disponible gratis. Esto permite que nosotros razonemos sobre ello en la misma manera normalmente íbamos. Por ejemplo, en el universo relativized de BQP, PPS todavía se cierran bajo unión e intersección. También es útil procurando ampliar el poder de una máquina con oráculos, porque los resultados bajos determinan cuando el poder de la máquina permanece lo mismo.

Véase también



Buscar