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 Bal costo unitario. En particular, esto significa que si B es bajo para A continuación, B está contenido en A . De manera informal, la humildad significa que los problemas en B no solo se pueden resolver con máquinas que pueden resolver problemas en A , sino que son “fáciles de resolver”. Una máquina A puede simular muchas consultas de Oracle a B sin exceder sus límites de recursos.
Los resultados y las relaciones que establecen una clase tan bajo para otro a menudo se llaman bajeza resultados. El conjunto de lenguajes bajo para una clase de complejidad A se denota Bajo (A) .
Clases que son bajas para ellas mismas
Se sabe que varias clases de complejidad natural son bajas por sí mismas. A esta clase a veces se la llama auto-baja . [2] Scott Aaronson llama a esta clase una clase de complejidad física . [3] Tenga en cuenta que ser auto-bajo es una condición más fuerte que estar cerrado por complemento . De manera informal, una clase que es baja en sí misma significa que un problema puede usar otros problemas en la clase como subrutinas de costo unitario sin exceder el poder de la clase de complejidad.
Se sabe que las siguientes clases son autobajas: [3]
- P es auto-bajo (es decir, P P = P) porque los algoritmos de tiempo polinomial están cerrados bajo composición: un algoritmo de tiempo polinomial puede hacer polinomialmente muchas consultas a otros algoritmos de tiempo polinómico, mientras retiene un tiempo de ejecución polinomial.
- PSPACE (con mecanismo de acceso restringido a Oracle) también es auto-bajo, y esto se puede establecer exactamente con el mismo argumento.
- L es auto-bajo porque puede simular consultas de Oracle en el espacio de registro en el espacio de registro, reutilizando el mismo espacio para cada consulta.
- NC también es auto-bajo por la misma razón.
- BPP 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 que sea un poco más difícil demostrar que BPP es bajo para sí mismo.
- De manera similar, el argumento a favor de BPP casi es válido para BQP , pero además tenemos que demostrar que las consultas cuánticas se pueden realizar en superposición coherente. [4]
- Ambos Paridad P () y BPP son bajos por sí mismos. Estos fueron importantes para mostrar el teorema de Toda . [5]
- NP ∩ coNP es bajo por sí mismo. [1]
Cada clase que es baja por sí misma se cierra bajo complemento , siempre que sea lo suficientemente potente como para negar el resultado booleano. Esto implica que NP no es bajo en sí mismo a menos que NP = co-NP , lo que se considera poco probable porque implica que la jerarquía polinomial colapsa al primer nivel, mientras que se cree ampliamente que la jerarquía es infinita. Lo contrario a esta afirmación no es cierto. Si una clase está cerrada por complemento, no significa que la clase sea baja por sí misma. Un ejemplo de tal clase es EXP , que está cerrada por complemento, pero no es baja por sí misma.
Clases que son bajas para otras clases de complejidad
Algunos de los resultados más complejos y famosos con respecto a la bajeza de clases 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 de isomorfismo gráfico es bajo para la paridad P (). [7] Esto significa que si podemos determinar si una máquina NP tiene un número par o impar de caminos aceptables, podemos resolver fácilmente el isomorfismo de grafos. De hecho, más tarde se demostró que el isomorfismo gráfico es bajo para ZPP NP . [8]
- El PP amplificado es bajo para el PP . [9]
- NP ∩ coNP es igual al conjunto de idiomas bajo para NP, es decir, Bajo (NP) = NP ∩ coNP. [1]
- AM ∩ coAM es bajo para ZPP NP . [1]
Aplicaciones
La bajeza es particularmente valiosa en los argumentos de relativización, donde puede usarse 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 sobre ello de la misma manera que lo haríamos normalmente. Por ejemplo, en el universo relativizado de BQP , PP todavía está cerrado bajo unión e intersección. También es útil cuando se busca expandir la potencia de una máquina con oráculos, porque los resultados bajos determinan cuándo la potencia de la máquina sigue siendo la misma.
Ver también
Referencias
- ↑ a b c d Köbler, Johannes; Torán, Jacobo (2015). "Resultados de la bajeza: la próxima generación". Boletín de la EATCS . 117 .
- ^ Rothe, J. (2006). Teoría de la complejidad y criptología: una introducción a la criptocomplejidad . Textos en Informática Teórica. Una serie EATCS. Springer Berlín Heidelberg. ISBN 978-3-540-28520-5. Consultado el 15 de mayo de 2017 .
- ^ a b http://www.scottaaronson.com/blog/?p=2070#comment-282988
- ^ Bernstein y Vazirani, Teoría de la complejidad cuántica, SIAM Journal on Computing , 26 (5): 1411-1473, 1997. [1]
- ^ [2]
- ^ L. Fortnow y JD Rogers. Limitaciones de complejidad en la computación cuántica. En Proceedings of IEEE Complexity '98 , p.202-209. 1998. arXiv : cs.CC/9811023 .
- ^ V. Arvind y P. Kurur. El isomorfismo gráfico está en SPP. ECCC TR02-037 . 2002.
- ^ Vikraman Arvind y Johannes Köbler. El isomorfismo del gráfico es bajo para ZPP (NP) y otros resultados bajos. Actas del 17 ° Simposio anual sobre aspectos teóricos de la informática , ISBN 3-540-67141-2 , p. 431-442. 2000.
- ^ L. Li. Sobre las funciones de conteo. Tesis de doctorado, Universidad de Chicago. 1993.