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 ]} Esta afirmación implica que una máquina abstracta que resuelve problemas en A no obtiene 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, la baja complejidad significa que los problemas en B no solo son resolubles 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 una clase como baja para otra se denominan a menudo resultados de baja . El conjunto de lenguajes bajos para una clase de complejidad A se denota Low(A) .

Se sabe que varias clases de complejidad natural son bajas para sí mismas, es decir B ^B = B. A esta clase a veces se la llama auto-baja . ^{[ 2 ]} Scott Aaronson llama a esta clase una clase de complejidad física . ^{[ 3 ]} Nótese que ser auto-baja es una condición más fuerte que ser cerrada bajo complemento . De manera informal, que una clase sea baja para sí misma significa que un problema puede usar otros problemas de la clase como subrutinas de costo unitario sin exceder la potencia de la clase de complejidad.

Se sabe que las siguientes clases son autoinferiores: ^{[ 3 ]}

• P es autobajo (es decir, P ^P = P) porque las funciones polinómicas son cerradas bajo composición , por lo que un algoritmo de tiempo polinómico puede realizar polinómicamente muchas consultas a otros algoritmos de tiempo polinómico, manteniendo al mismo tiempo un tiempo de ejecución general polinómico.
• PSPACE (con mecanismo de acceso restringido al oráculo) también es auto-bajo, y esto se puede establecer con el mismo argumento.
• L es auto-bajo porque puede simular consultas de oráculo en espacio de registro en espacio de registro, reutilizando el mismo espacio para cada consulta.
• NC también es autobajo por la misma razón.
• El ZPP también es bajo en sí mismo y los mismos argumentos casi funcionan para el BPP , pero hay que tener en cuenta los errores, lo que hace que sea un poco más difícil demostrar que el BPP es bajo en 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 ]}
• Ambos Paridad P (${\displaystyle {\oplus }{\hbox{P}}}$) y BPP son bajos para sí mismos. Estos fueron importantes para demostrar el teorema de Toda . ^{[ 5 ]}
• NP ∩ coNP es bajo para sí mismo. ^{[ 1 ]}

Toda clase que sea baja para sí misma es cerrada bajo el complemento , siempre que sea lo suficientemente potente como para negar el resultado de una consulta booleana. Esto implica que NP no es baja para sí misma a menos que NP = co-NP , lo cual se considera improbable porque implica que la jerarquía polinómica se reduce al primer nivel, mientras que se cree ampliamente que la jerarquía es infinita. Lo contrario de esta afirmación no es cierto. Si una clase es cerrada bajo el complemento, no significa que sea baja para sí misma. Un ejemplo de tal clase es EXPTIME , que es cerrada bajo el complemento, pero no es baja para sí misma.

Algunos de los resultados más complejos y conocidos en relación con la baja categoría de las clases sociales 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 de tiempo polinomial 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 la paridad P (${\displaystyle {\oplus }{\hbox{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, posteriormente se demostró que el isomorfismo de grafos es bajo para ZPP ^NP . ^{[ 8 ]}
• La PP amplificada es baja para PP . ^{[ 9 ]}
• NP ∩ coNP es igual al conjunto de lenguajes 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 usar para establecer que el poder de una clase no cambia en el "universo relativizado" donde una máquina oracular específica está disponible gratuitamente. Esto nos permite razonar sobre la clase de la misma manera que lo haríamos normalmente. Por ejemplo, en el universo relativizado de BQP , PP sigue siendo cerrado bajo la unión y la intersección. También es útil al buscar 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)