Hiérarchie uniforme des problèmes couvrant la complexité et les hiérarchies de calcul

Quelqu'un connaît-il un ensemble de problèmes qui varient uniformément et qui couvrent l'une des hiérarchies "intéressantes" de complexité et de calculabilité? Par intéressant, je veux dire, par exemple, la hiérarchie polynomiale, la hiérarchie arithmétique ou la hiérarchie analytique. Ou peut-être (N) P, (N) EXP, 2 (N) EXP,$\ldots$

Plus concrètement: vous pouvez donner un ensemble uniforme de problèmes qui caractérisent la hiérarchie arithmétique: . Mais ceux-ci ne sont pas toujours les plus utiles pour réduire les problèmes réels.$0, 0', \overline{0'}, 0'', \overline{0''},\ldots$

D'un autre côté, le livre de Harel, Kozen et Tiuryn ​​présente un ensemble de problèmes de pavage variables qui sont NP, $\Pi^0_1$ , $\Sigma^0_2$ et $\Sigma^1_1$ complets. Les problèmes sont utiles pour montrer les réductions, mais il n'est pas tout à fait clair s'ils se généralisent uniformément pour couvrir les autres niveaux des hiérarchies dans lesquelles ils se trouvent.

Quelqu'un connaît-il un tel ensemble de problèmes concrets et uniformes qui s'étendent sur une hiérarchie?

EDIT: Juste pour clarifier, je sais que les 3 hiérarchies que je donne avant tout ont des définitions standard en termes de force de quantification alternée. Ce n'est pas ce que je recherche. Je cherche quelque chose de différent, comme un jeu sur un graphique ou un puzzle joué avec des pavages.

[S'appuyant sur la perspicacité de Kaveh dans les commentaires.] Il semble peu probable que quelqu'un puisse trouver une famille de problèmes qui soit significativement différente de la formule booléenne quantifiée, sans réfuter l'analogue PH de la conjecture d'isomorphisme de Berman-Hartmanis. Sans cela, tout problème que vous rencontrez serait non seulement équivalent à , mais en fait isomorphe à celui-ci. Une façon de définir l'isomorphisme entre deux langues ici est de prendre un seul langage abstrait, mais de coder ses objets (dans ce cas, des formules booléennes quantifiées) en utilisant deux codages booléens différents.$QBF_k$

D'un autre côté, l'isomorphisme n'est pas nécessairement un bon juge de ce qui est utile aux gens pour trouver des preuves. Après tout, dans la hiérarchie arithmétique, le théorème d'isomorphisme de Myhill prouve l'analogue arithmétique de la conjecture d'isomorphisme BH (en fait, c'est l'histoire à l'envers puisque BH a été motivé par Myhill). Pourtant, comme le souligne la question, il existe plusieurs caractérisations "d'apparence différente" de différents niveaux, dont certaines sont plus utiles pour les preuves que d'autres.

Bien qu'il semble peu probable que quiconque propose une famille de langues aussi uniforme pour chaque niveau de PH, les deux enquêtes ( une , deux ) de Schaefer et Umans discutent de problèmes naturels qui au moins "semblent différents" de QBF pour les premiers niveaux de PH.