Requisitos de tempo / espaço para verificar ou falsificar uma declaração de primeira ordem

Embora L.Berman tenha provado que o problema de verificar ou falsificar qualquer declaração de primeira ordem sobre números reais que usa adição e comparação, mas não multiplicação, está no EXPSPACE. Foi mostrado quanto tempo ou espaço você precisaria para verificar ou falsificar qualquer declaração de primeira ordem sobre números reais que usa comparação de adição E multiplicação?

A teoria dos campos fechados reais (RCF) está completa para a teoria de primeira ordem dos números reais no idioma que você descreveu. Portanto, é equivalente a verificar se o RCF prova a fórmula.

Pela eliminação do quantificador de Tarski para RCF, isso pode ser calculado. A complexidade dos algoritmos de Tarski não é elementar e há um limite inferior duplamente exponencial para o problema.

Um algoritmo mais eficiente do que o algoritmo de Tarski é dado por Saugata Basu " Um algoritmo aprimorado para eliminação de quantificadores em campos reais fechados ", FOCS 1997 (que parece quase ideal, consulte o Teorema 1) (um rascunho do artigo está disponível aqui ).

Verifique também Saugata Basu, " Novos Resultados na Eliminação do Quantificador em Campos Real Fechados e Aplicações em Bancos de Dados de Restrições ", Journal of the ACM, 1999.