Klasa złożoności syntaktycznej

Wiadomo, że niektóre (nie relatywizowane) klasy złożoności składniowej między i P S P A C E mają następującą właściwość, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Zastanawiam się, czy istnieje (nierelatywizowana) klasa złożoności składniowej X taka, że P P ⊆ X ⊆ P S P A C ${\bf P}$${\bf PSPACE}$${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$${\bf X}$${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$? Jakie są implikacje istnienia lub nieistnienia klasy złożoności ? ${\bf X}$

Jedną z takich klas jest hierarchia zliczania . Jest zdefiniowany jako połączenie hierarchii, która jest zdefiniowana podobnie do hierarchii wielomianowej:$\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}$

Hierarchia liczenia ma niezłą charakterystykę składniową dzięki H. Vollmerowi i K. Wagnerowi „Teoretyczne charakterystyki rekurencji klas złożoności funkcji zliczających”, Theoretical Computer Science 163: 245-258, 1996 : jest zbiorem - - funkcje wartościowane w zamknięciu podstawowych funkcji arytmetycznych w składzie i ograniczonych sumach.$\mathsf{CH}$$0$$1$$0,1,+,-,\cdot$