Requisitos de tiempo / espacio para verificar o falsificar una declaración de primer orden

Aunque L.Berman demostró que el problema de verificar o falsificar cualquier declaración de primer orden sobre números reales que usa la suma y la comparación pero no la multiplicación está en EXPSPACE. ¿Se le ha mostrado cuánto tiempo o espacio necesitaría para verificar o falsificar cualquier enunciado de primer orden sobre números reales que use la comparación de suma Y la multiplicación?

La teoría de los campos cerrados reales (RCF) está completa para la teoría de primer orden de los números reales en el lenguaje que usted describió. Por lo tanto, es equivalente a verificar si RCF prueba la fórmula.

Mediante la eliminación del cuantificador de Tarski para RCF, esto se puede calcular. La complejidad de los algoritmos de Tarski no es elemental y existe un límite inferior doblemente exponencial para el problema.

Saugata Basu ofrece un algoritmo más eficiente que el algoritmo de Tarski " Un algoritmo mejorado para la eliminación del cuantificador sobre campos cerrados reales ", FOCS 1997 (que parece ser casi óptimo, ver Teorema 1) (un borrador del documento está disponible aquí ).

Consulte también Saugata Basu, " Nuevos resultados sobre la eliminación del cuantificador sobre campos cerrados reales y aplicaciones para restringir bases de datos ", Journal of the ACM, 1999.