Jerarquía uniforme de problemas que abarcan complejidad y jerarquías computacionales

¿Alguien sabe de un conjunto de problemas que varían uniformemente y abarcan una de las jerarquías "interesantes" de complejidad y computabilidad? Por interesante, quiero decir, por ejemplo, la Jerarquía Polinómica, la Jerarquía Aritmética o la Jerarquía Analítica. O tal vez (N) P, (N) EXP, 2 (N) EXP,$\ldots$

Más concretamente: puede dar un conjunto uniforme de problemas que caracterizan la jerarquía aritmética: . Pero estos no siempre son los más útiles para reducir a problemas reales.$0, 0', \overline{0'}, 0'', \overline{0''},\ldots$

Por otro lado, el libro de Harel, Kozen y Tiuryn ​​tiene un conjunto de problemas de mosaico variables que son NP, $\Pi^0_1$ , $\Sigma^0_2$ y $\Sigma^1_1$ completos. Los problemas son útiles para mostrar reducciones, pero no está del todo claro si se generalizan uniformemente para cubrir los otros niveles de las jerarquías en las que se sientan.

¿Alguien sabe de un conjunto de problemas concretos y uniformes que abarquen una jerarquía?

EDITAR: Solo para aclarar, sé que las 3 jerarquías que doy sobre todo tienen definiciones estándar en términos de fuerza cuantificadora alterna. Eso no es lo que estoy buscando. Estoy buscando algo diferente, como un juego en un gráfico o un rompecabezas jugado con lazos.

[Partiendo de la visión de Kaveh en los comentarios.] Parece poco probable que alguien pueda encontrar una familia de problemas que sea significativamente diferente de la fórmula booleana cuantificada, sin refutar el análogo de PH de la conjetura del isomorfismo de Berman-Hartmanis. Sin eso, cualquier problema que no solo sería equivalente a , sino que de hecho sería isomorfo. Una forma de definir el isomorfismo entre dos idiomas aquí es tomar un solo lenguaje abstracto, pero codificar sus objetos (en este caso, fórmulas booleanas cuantificadas) usando dos codificaciones booleanas diferentes.$QBF_k$

Por otro lado, el isomorfismo no es necesariamente un buen juez de lo que es útil para que las personas presenten pruebas. Después de todo, en la jerarquía aritmética, el Teorema del isomorfismo de Myhill demuestra el análogo aritmético de la conjetura del isomorfismo de BH (de hecho, eso es historia al revés ya que BH fue motivado por Myhill). Sin embargo, como señala la pregunta, hay varias caracterizaciones de "aspecto diferente" de varios niveles, algunas de las cuales son más útiles para las pruebas que otras.

Aunque parece poco probable que alguien presente una familia de idiomas tan uniforme para cada nivel de PH, las dos encuestas ( una , dos ) de Schaefer y Umans discuten problemas naturales que al menos "parecen diferentes" de QBF para los primeros niveles de PH.