Baja (complejidad)

En la teoría de la complejidad computacional , se dice que un lenguaje B (o una clase de complejidad B ) es bajo para una clase de complejidad A (con alguna versión relativizada razonable de A ) si A ^B = A ; es decir, A con un oráculo para B es igual a A. ^[1] Tal afirmación implica que una máquina abstracta que resuelve problemas en A no logra potencia adicional si se le da la capacidad de resolver problemas en B a un costo unitario. En particular, esto significa que si B es bajo para A, entonces B está contenido en A. De manera informal, bajo significa que los problemas en B no solo son solucionables por máquinas que pueden resolver problemas en A , sino que son "fáciles de resolver". Una máquina A puede simular muchas consultas de oráculo a B sin exceder sus límites de recursos.

Los resultados y las relaciones que establecen que una clase es baja para otra suelen denominarse resultados de baja complejidad . El conjunto de lenguajes bajos para una clase de complejidad A se denota como Bajo(A) .

Se sabe que varias clases de complejidad natural son bajas por sí mismas. A este tipo de clases se las denomina a veces autobajas . ^[2] Scott Aaronson denomina a estas clases clases de complejidad física . ^[3] Nótese que ser autobaja es una condición más fuerte que ser cerrada bajo complemento . De manera informal, una clase que es baja por sí misma significa que un problema puede usar otros problemas en la clase como subrutinas de costo unitario sin exceder la potencia de la clase de complejidad.

Se sabe que las siguientes clases son autodenominadas bajas: ^[3]

• P es autobajo (es decir, P ^P = P) porque los algoritmos de tiempo polinomial están cerrados bajo composición: un algoritmo de tiempo polinomial puede realizar una cantidad polinomial de consultas a otros algoritmos de tiempo polinomial, mientras conserva un tiempo de ejecución polinomial.
• PSPACE (con mecanismo de acceso de oráculo restringido) también es autodeterminado y esto se puede establecer exactamente con el mismo argumento.
• L es autodenominado bajo porque puede simular consultas de Oracle en el espacio de registro, reutilizando el mismo espacio para cada consulta.
• NC también es auto-bajo por la misma razón.
• ZPP también es bajo para sí mismo y los mismos argumentos casi funcionan para BPP , pero hay que tener en cuenta los errores, lo que hace un poco más difícil demostrar que BPP es bajo para sí mismo.
• De manera similar, el argumento para BPP casi se aplica a BQP , pero tenemos que demostrar adicionalmente que las consultas cuánticas se pueden realizar en superposición coherente. ^[4]
• Tanto la paridad P ( ) como el BPP son bajos por sí mismos. Estos fueron importantes para demostrar el teorema de Toda . ^[5]${\displaystyle {\oplus} {\hbox{P}}}$
• NP ∩ coNP es bajo por sí mismo. ^[1]

Toda clase que sea baja para sí misma está cerrada bajo complemento , siempre que sea lo suficientemente potente como para negar el resultado booleano. Esto implica que NP no es baja para sí misma a menos que NP = co-NP , lo que se considera improbable porque implica que la jerarquía polinómica colapsa al primer nivel, mientras que se cree ampliamente que la jerarquía es infinita. La inversa de esta afirmación no es cierta. Si una clase está cerrada bajo complemento, no significa que la clase sea baja para sí misma. Un ejemplo de una clase de este tipo es EXP , que está cerrada bajo complemento, pero no es baja para sí misma.

Algunos de los resultados más complejos y famosos en relación con el nivel de clases bajas incluyen:

• BQP es bajo para PP ^{[6] En otras palabras, un programa basado en tomar la decisión mayoritaria de un número ilimitado de iteraciones de un} algoritmo aleatorio politemporal puede resolver fácilmente todos los problemas que una computadora cuántica puede resolver de manera eficiente.
• El problema del isomorfismo de grafos es bajo para Paridad P ( ). ^[7] Esto significa que si podemos determinar si una máquina NP tiene un número par o impar de caminos de aceptación, podemos resolver fácilmente el isomorfismo de grafos. De hecho, más tarde se demostró que el isomorfismo de grafos es bajo para ZPP ^NP . ^[8]${\displaystyle {\oplus} {\hbox{P}}}$
• El PP amplificado es bajo para PP . ^[9]
• NP ∩ coNP es igual al conjunto de idiomas bajos para NP, es decir, Low(NP) = NP ∩ coNP. ^[1]
• AM ∩ coAM es bajo para ZPP ^NP . ^[1]

La baja potencia es particularmente valiosa en los argumentos de relativización, donde se puede utilizar para establecer que el poder de una clase no cambia en el "universo relativizado" donde una máquina oráculo particular está disponible de forma gratuita. Esto nos permite razonar al respecto de la misma manera en que lo haríamos normalmente. Por ejemplo, en el universo relativizado de BQP , PP sigue estando cerrado bajo unión e intersección. También es útil cuando se busca expandir el poder de una máquina con oráculos, porque los resultados de baja potencia determinan cuándo el poder de la máquina permanece igual.

• Baja (computabilidad)