Complexité syntaxique Classe

Il est connu que certaines classes de complexité syntaxique (non relativisées) entre et P S P A C E ont la propriété suivante, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Je me demande s'il existe une classe de complexité syntaxique (non relativisée) X telle que 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}$? Quelles sont les implications de l'existence ou de la non-existence de la classe de complexité ? ${\bf X}$

Une telle classe est la hiérarchie de comptage . Il est défini comme l'union d'une hiérarchie définie de manière similaire à la hiérarchie polynomiale:$\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}$

La hiérarchie de comptage a une belle caractérisation syntaxique due à H. Vollmer et K. Wagner "Caractérisations théoriques de la récursivité des classes de complexité des fonctions de comptage", Theoretical Computer Science 163: 245-258, 1996 : ist the set of 0 - 1 - fonctions valorisées dans la fermeture des fonctions arithmétiques de base 0 , 1 , + , - , ⋅ sous composition et sommes bornées.$\mathsf{CH}$$0$$1$$0,1,+,-,\cdot$