Se sabe que algunas clases de complejidad sintáctica (no relativizadas) entre y P S P A C E tienen la siguiente propiedad, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Me pregunto si existe una clase de complejidad sintáctica (no relativizada) X tal que P P ⊆ X ⊆ P S P A C E? ¿Cuáles son las implicaciones de la existencia o no existencia de complejidad clase ?
cc.complexity-theory
complexity-classes
Tayfun Pay
fuente
fuente
Respuestas:
Una de esas clases es la jerarquía de conteo . Se define como la unión de una jerarquía que se define de manera similar a la jerarquía polinómica:CH
La jerarquía de conteo tiene una buena caracterización sintáctica debido a H. Vollmer y K. Wagner "Caracterizaciones teóricas de recursión de clases de complejidad de funciones de conteo", Theoretical Computer Science 163: 245-258, 1996 : es el conjunto de - - funciones valoradas en el cierre de funciones aritméticas básicas bajo composición y sumas acotadas.CH 0 1 0,1,+,−,⋅
fuente