Syntaktische Komplexitätsklasse so dass

Es ist bekannt, dass einige (nicht relativierte) syntaktische Komplexitätsklassen zwischen ${\bf P}$ und ${\bf PSPACE}$ die folgende Eigenschaft haben: ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$ . Ich frage mich, ob es eine (nicht relativierte) syntaktische Komplexitätsklasse ${\bf X}$ so dass ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$ ? Was bedeutet die Existenz oder Nichtexistenz der Komplexitätsklasse ${\bf X}$ ?

Eine derartige Klasse ist der Zähl- Hierarchie . Es ist definiert als die Vereinigung einer Hierarchie, die ähnlich wie die Polynomhierarchie definiert ist:$\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}$

Die Zählhierarchie hat eine schöne syntaktische Charakterisierung aufgrund von H. Vollmer und K. Wagner "Rekursionstheoretische Charakterisierungen von Komplexitätsklassen von ", Theoretical Computer Science 163: 245-258, 1996 : ist die Menge von - bewertete Funktionen beim Schließen von arithmetischen Grundfunktionen unter Zusammensetzung und begrenzten Summen.$\mathsf{CH}$$0$$1$$0,1,+,-,\cdot$