Dapatkah versi kompleksitas teorema Rice digunakan untuk memisahkan AC0 dan PSPACE?

Dalam pertanyaan ini , disebutkan bahwa ada versi kompleksitas deskriptif teorema Rice. Saya menemukan bukti teorema berikut:

Diberikan kompleksitas kelas C , properti nontrivial dari bahasa dalam C tidak dapat dihitung dalam C

Saya sebelumnya telah memposting bukti yang saya temukan, tetapi karena begitu lama dan karena ditunjukkan dalam komentar bahwa makalah ini berisi bukti teorema itu, saya menghapusnya. (Jika karena alasan tertentu Anda putus asa untuk melihat bukti saya, silakan lihat revisi sebelumnya dari pertanyaan ini.)

Ketertarikan saya adalah apakah teorema ini dapat digunakan untuk memisahkan AC0 dan PSPACE. Inilah argumennya:

Pertimbangkan properti P dari kelas kompleksitas AC0 yang didefinisikan sebagai berikut:

P : properti menjadi kueri FO yang menerima struktur tetap tertentu, yaitu struktur yang terdiri dari satu elemen, tidak ada fungsi, tidak ada konstanta, dan tidak ada hubungan

Jelas, dengan teorema di atas, P tidak dapat ditentukan dalam AC0; ini adalah properti non-sepele dari kueri FO.

Namun, sedikit pemeriksaan harus menunjukkan bahwa menghitung apakah permintaan FO menerima struktur sederhana seperti itu dapat diputuskan semudah TQBF; dengan demikian, P dapat dipilih dalam PSPACE.

Untuk memastikan kejelasan tentang hal ini (bahwa P dapat dihitung dalam PSPACE): Perhatikan bahwa properti yang kami minati mengharuskan strukturnya menjadi FO. Jadi, kami mencoba menentukan apakah kueri FO yang berjalan pada struktur elemen tunggal tanpa hubungan menerima. Karena tidak ada hubungan yang harus dihadapi, harus jelas bahwa tugas untuk memutuskan permintaan FO seperti itu setara dengan memutuskan sebuah instance dari TQBF; tidak ada hubungan, jadi satu-satunya tantangan yang tersisa adalah untuk mengevaluasi apakah rumus boolean yang dikuantifikasi benar atau tidak. Ini pada dasarnya hanya TQBF, jadi P dapat dihitung dalam PSPACE.

Karena P dapat dihitung dalam PSPACE tetapi bukan AC0, kita harus dapat menyimpulkan bahwa AC0! = PSPACE. Apakah alasan ini benar, atau apakah saya membuat kesalahan di suatu tempat? Saya khususnya prihatin dengan paragraf sebelumnya; Saya akan mencoba untuk mengklarifikasi dan memperbarui argumen besok setelah saya mendapatkan kesempatan untuk memberikan sedikit lebih banyak pemikiran pada eksposisi.

Saya akan menerima sebagai jawaban contoh dari permintaan FO yang, ketika menghitung pada satu elemen, struktur bebas hubungan yang telah saya jelaskan, jelas tidak masuk akal sebagai contoh dari TQBF. (Saya menyarankan bahwa tidak ada satu, jadi jika Anda dapat menunjukkan bahwa ada satu, itu akan menjadi contoh tandingan.)

Terima kasih.

Memutuskan properti nontrivial dari (pengindeksan) yang ditetapkan dalam kelas kompleksitas sama sulitnya dengan menghitung grafik fungsi universal untuk kelas tersebut. Secara intuitif ini berarti bahwa satu-satunya cara untuk memutuskan properti nontrivial adalah dengan mensimulasikan mesin dan menunggu jawaban. Tampaknya bagi saya bahwa gagasan untuk menggunakan properti semacam itu hanya akan memberikan apa yang dikenal oleh teorema hierarki. (Lihat teorema 4.2 dari D. Kozen, " Pengindeksan kelas subkursif ", 1978 untuk rincian dan pernyataan yang tepat dari teorema.)

$grU_{AC^0}$$AC^0$$PSpace$$AC^0 \subseteq L$$L$$PSpace$$AC^0$$AC^0$$FO$$PSpace$$PSpace$$AC^0$$AC^0$$PSapce$

$AC^0 \subseteq L \subset PSpace$