Einheitliche Hierarchie von Problemen, die Komplexität und Rechenhierarchien umfassen

Kennt jemand eine Reihe von Problemen, die einheitlich variieren und eine der "interessanten" Hierarchien von Komplexität und Berechenbarkeit umfassen? Mit interessant meine ich zum Beispiel die Polynomhierarchie, die arithmetische Hierarchie oder die analytische Hierarchie. Oder vielleicht (N) P, (N) EXP, 2 (N) EXP, $\ldots$

$0, 0', \overline{0'}, 0'', \overline{0''},\ldots$

Andererseits weist das Buch von Harel, Kozen und Tiuryn ​​eine Reihe unterschiedlicher Kachelprobleme auf, die NP, , und . Die Probleme sind nützlich, um Reduzierungen anzuzeigen, aber es ist nicht ganz klar, ob sie einheitlich verallgemeinert werden, um die anderen Ebenen der Hierarchien abzudecken, in denen sie sitzen.$\Pi^0_1$$\Sigma^0_2$$\Sigma^1_1$

Kennt jemand eine solche Reihe konkreter, einheitlicher Probleme, die sich über eine Hierarchie erstrecken?

EDIT: Nur zur Verdeutlichung weiß ich, dass die 3 Hierarchien, die ich vor allem gebe, Standarddefinitionen in Bezug auf die Stärke des alternierenden Quantifizierers haben. Das suche ich nicht. Ich suche etwas anderes, wie ein Spiel in einer Grafik oder ein Puzzle, das mit Kacheln gespielt wird.

[Aufbauend auf Kavehs Einsicht in den Kommentaren.] Es ist unwahrscheinlich, dass jemand eine Familie von Problemen findet, die sich erheblich von der quantifizierten Booleschen Formel unterscheidet, ohne das PH-Analogon der Berman-Hartmanis-Isomorphismus-Vermutung zu widerlegen. Ohne das wäre jedes Problem, das Sie sich einfallen lassen, nicht nur gleichbedeutend mit , sondern tatsächlich isomorph dazu. Eine Möglichkeit, den Isomorphismus zwischen zwei Sprachen zu definieren, besteht darin, eine einzelne abstrakte Sprache zu verwenden, ihre Objekte (in diesem Fall quantifizierte Boolesche Formeln) jedoch mit zwei verschiedenen Booleschen Codierungen zu codieren.$QBF_k$

Auf der anderen Seite ist Isomorphismus nicht unbedingt ein guter Richter darüber, was für Menschen nützlich ist, um Beweise zu finden. Schließlich beweist Myhills Isomorphismus-Theorem in der arithmetischen Hierarchie das arithmetische Analogon der BH-Isomorphismus-Vermutung (tatsächlich ist das Geschichte rückwärts, da BH von Myhill motiviert wurde). Wie die Frage zeigt, gibt es jedoch mehrere "unterschiedlich aussehende" Charakterisierungen auf verschiedenen Ebenen, von denen einige für Beweise nützlicher sind als andere.

Obwohl es unwahrscheinlich ist, dass irgendjemand für jedes PH-Niveau eine so einheitliche Sprachfamilie findet, diskutieren die beiden Umfragen ( eins , zwei ) von Schaefer und Umans natürliche Probleme, die in den ersten paar Fällen zumindest "anders aussehen" als QBF PH-Werte.