¿Podría usarse una versión de complejidad descriptiva del teorema de Rice para separar AC0 y PSPACE?

10

En esta pregunta , se mencionó que existen versiones descriptivas de complejidad del teorema de Rice. Encontré una prueba del siguiente teorema:

Dada una clase de complejidad C , las propiedades no triviales de los lenguajes en C no se pueden calcular en C

Anteriormente había publicado la prueba que encontré, pero debido a que era tan larga y porque se señaló en los comentarios que este documento ya contiene una prueba de ese teorema, la eliminé. (Si por alguna razón está desesperado por ver mi prueba, consulte las revisiones anteriores de esta pregunta).

Mi interés está en si este teorema podría o no usarse para separar AC0 y PSPACE. Aquí está el argumento:

Considere la propiedad P de la clase de complejidad AC0 definida como sigue:

P : la propiedad de ser una consulta FO que acepta una estructura fija particular, es decir, la estructura que consta de un elemento, sin funciones, sin constantes y sin relaciones

Claramente, según el teorema anterior, P no es decidible en AC0; Es una propiedad no trivial de las consultas FO.

Sin embargo, un pequeño examen debería mostrar que calcular si una consulta FO acepta o no una estructura tan simple se puede decidir tan fácilmente como TQBF; así, P es decidible en PSPACE.

Para garantizar la claridad en este punto (que P es computable en PSPACE): Tenga en cuenta que la propiedad que nos interesa requiere que la estructura sea FO. Por lo tanto, estamos tratando de determinar si una consulta FO que se ejecuta en una estructura de elemento único sin relaciones acepta. Debido a que no hay relaciones con las que lidiar, debe quedar claro que la tarea de decidir una consulta FO de este tipo es equivalente a decidir una instancia de TQBF; no hay relaciones, por lo que el único desafío que queda es evaluar si la fórmula booleana cuantificada es verdadera o no. Esto es básicamente solo TQBF, por lo que P es computable en PSPACE.

Como P es computable en PSPACE pero no en AC0, deberíamos poder concluir que AC0! = PSPACE. ¿Es correcto este razonamiento o he cometido un error en alguna parte? Estoy particularmente preocupado por el párrafo anterior; Trataré de aclarar y actualizar el argumento mañana después de que tenga la oportunidad de pensar un poco más en la exposición.

Aceptaría como respuesta un ejemplo de una consulta FO que, cuando se computa en la estructura de un elemento, libre de relaciones que he descrito, claramente no tiene sentido como una instancia de TQBF. (Estoy sugiriendo que no hay uno, así que si puedes demostrar que hay uno, sería un contraejemplo).

Gracias.

cc.complexity-theory complexity-classes descriptive-complexity separation Philip White
fuente
@Kaveh: Debes hacer que tu comentario sea una respuesta.
Dai Le
@Kaveh: Gracias por tu comentario. Sin embargo, estoy un poco confundido por lo que estás diciendo. ¿A qué máquina en PSPACE para conjuntos AC0 te referías? Me refería a la propiedad P, que se relaciona específicamente con consultas FO sobre estructuras muy simples. Estoy sugiriendo que evaluar si las consultas FO aceptan una estructura simple está garantizado como TQBF, que es PSPACE. No veo dónde se necesita un simulador universal para AC0.
Philip White
@Kaveh: OK. Prepararé mi intento de prueba de la conjetura en esta pregunta y la publicaré como una pregunta separada. Pensé que era correcto, pero a menudo me equivoco. (Por supuesto, si refutas mi conjetura antes de eso, no me molestaré)
Philip White,
Oh. Acabo de publicarlo como una pregunta. ¿Debo eliminar la nueva pregunta y publicarla como respuesta?
Philip White
(Lo eliminé y lo agregué a esta pregunta)
Philip White

Respuestas:

7

Decidir las propiedades no triviales de (una indexación) de conjuntos en una clase de complejidad es tan difícil como calcular el gráfico de la función universal para la clase. Intuitivamente, esto significa que la única forma de decidir una propiedad no trivial es simular las máquinas y esperar respuestas. Me parece que la idea de usar una propiedad así solo dará lo que se conoce por los teoremas de jerarquía. (Ver el teorema 4.2 de D. Kozen, " Indexación de clases subrecursivas ", 1978 para detalles y la declaración exacta del teorema).

grUAC0AC0PSpaceAC0⊆LLPSpaceAC0AC0FOPSpacePSpaceAC0AC0PSapce

AC0⊆L⊂PSpace

Kaveh
fuente
Interesante, gracias. Entonces estás diciendo: 1) Mi argumento era correcto, pero 2) Había una manera más fácil. :) Creo que necesito repasar el teorema de la jerarquía espacial.
Philip White
FO
Vale genial. De hecho, acabo de comprobar la definición de FO. Sabía que incluía el símbolo de igualdad; Es por eso que requería que la estructura fuera un solo elemento. De esta manera, cualquier afirmación sobre la igualdad de dos variables no afectará la verdad de la consulta.
Philip White
Un comentario adicional ... usted hizo un punto importante sobre los símbolos no lógicos. Como no hay relaciones, el símbolo de igualdad es realmente esencial. En particular, es necesario expresar los literales muy booleanos que se necesitan para expresar TQBF.
Philip White
FO