Complexidade sintática Classe

Sabe-se que algumas classes de complexidade sintática (não relativizadas) entre e P S P A C E têm a seguinte propriedade, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Gostaria de saber se existe uma classe de complexidade sintática (não relativizada) X tal 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}$? Quais são as implicações da existência ou não da classe de complexidade ? ${\bf X}$

Uma tal classe é a hierarquia de contagem . É definida como a união de uma hierarquia definida de forma semelhante à hierarquia 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}$

A hierarquia de contagem tem uma boa caracterização sintática devido a H. Vollmer e K. Wagner "recursão caracterizações teóricas de classes de complexidade de funções de contagem", teórica Computer Science 163: 245-258, 1996 : ist o conjunto de 0 - 1 - funções valorizadas no fechamento das funções aritméticas básicas 0 , 1 , + , - , ⋅ sob composição e somas delimitadas.$\mathsf{CH}$$0$$1$$0,1,+,-,\cdot$