¿Resolver la clase de complejidad TODOS colapsa todos los grados de Turing?

Question

Me encontré con este papel de Scott Aaronson y aunque no entiendo nada de informática cuántica, el hecho de que existiera un modelo (incluso hipotético y probablemente irrealizable) de ALL que afirma, teórico o no, que resuelve ALL .

Porque ALL se define aparentemente como la clase (acertadamente) de todos los problemas de decisión, esto parece trascender completamente todos los Grados de Turing y el jerarquía aritmética lo que me deja estupefacto porque es la primera vez que oigo hablar de un método, hipercomputacional o no, que haga eso.

Así que mi pregunta es doble:

1. Resuelve ALL ¿realmente hace lo que acabo de exponer más arriba, en particular trasciende todos los oráculos?
2. ¿Lo hace el planteamiento expuesto en el documento?

Answer 1

Sí, su interpretación es correcta. Tenga en cuenta que los "programas" permitidos en este trabajo no pueden describirse utilizando una cantidad finita de información, ya que incluyen una secuencia infinita de "estados cuánticos de asesoramiento" (uno para cada longitud posible de entrada). Obsérvese que si se permite esa información adicional sin límite en su longitud, es trivial que se pueda calcular cualquier lenguaje: basta con dejar que el estado de asesoramiento para entradas de longitud $n$ codifican lo que deben ser todas las salidas en entradas de longitud $n$ . En este caso, el resultado es más sorprendente, ya que el tamaño del estado de asesoramiento se limita a ser polinomial en $n$ pero aún así no es demasiado chocante.