Persyaratan Waktu / Ruang untuk Memverifikasi atau Memalsukan Pernyataan Orde Pertama

Meskipun L.Berman membuktikan bahwa masalah memverifikasi atau memalsukan pernyataan urutan pertama tentang bilangan real yang menggunakan penambahan dan perbandingan tetapi tidak multiplikasi ada di EXPSPACE. Apakah sudah diperlihatkan berapa banyak waktu atau ruang yang akan Anda perlukan untuk memverifikasi atau memalsukan pernyataan orde pertama tentang bilangan real yang menggunakan perbandingan penambahan dan penggandaan?

Teori bidang tertutup nyata (RCF) lengkap untuk teori urutan pertama bilangan real dalam bahasa yang Anda gambarkan. Karena itu sama dengan memeriksa apakah RCF membuktikan formula.

Dengan eliminasi quantifier Tarski untuk RCF ini dapat dihitung. Kompleksitas algoritma Tarski adalah non-elementer dan ada lowerbound eksponensial ganda untuk masalah tersebut.

Algoritma yang lebih efisien daripada algoritma Tarski diberikan oleh Saugata Basu " Algoritma yang Ditingkatkan untuk Penghapusan Kuantifikasi Terhadap Bidang Tertutup Nyata ", FOCS 1997 (yang tampaknya hampir optimal, lihat Teorema 1) (draft makalah tersedia di sini ).

Juga periksa Saugata Basu, " Hasil Baru pada Penghapusan Eliminasi Atas Bidang Tertutup Nyata dan Aplikasi untuk Membatasi Database ", Jurnal ACM, 1999.