Kompleksitas Sintaksis Kelas

Diketahui bahwa beberapa kelas kompleksitas sintaksis (tidak berhubungan) antara ${\bf P}$ dan ${\bf PSPACE}$ memiliki properti berikut, ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$ . Saya bertanya-tanya apakah ada kompleksitas sintaksis (non-relativized) kelas ${\bf X}$ sehingga ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$? Apa implikasi dari keberadaan atau tidak adanya kompleksitas kelas ${\bf X}$ ?

Salah satu kelas tersebut adalah hierarki penghitungan . Ini didefinisikan sebagai penyatuan hierarki yang didefinisikan sama dengan hierarki polinomial:$\mathsf{CH}$

• $\mathsf{C}_{0}\mathsf{P} := \mathsf{PP}$ ,
• $\mathsf{C}_{i+1}\mathsf{P} := \mathsf{PP}^{\mathsf{C}_{i}\mathsf{P}}$
• $\mathsf{CH} := \bigcup_i \mathsf{C}_{i}\mathsf{P}$

Hirarki penghitungan memiliki karakterisasi sintaksis yang bagus karena H. Vollmer dan K. Wagner "Karakterisasi teoretis rekursi dari kelas kompleksitas fungsi penghitungan", Theoretical Computer Science 163: 245-258, 1996 : adalah himpunan - fungsi bernilai dalam penutupan fungsi aritmatika dasar bawah komposisi dan jumlah terikat. 0 1 0 , 1 , + , - , $\mathsf{CH}$$0$$1$$0,1,+,-,\cdot$