Jednolita hierarchia problemów obejmujących złożoność i hierarchie obliczeniowe

Czy ktoś zna zestaw problemów, które różnią się równomiernie i obejmują jedną z „interesujących” hierarchii złożoności i obliczalności? Przez interesujące rozumiem na przykład Hierarchię Wielomianową, Hierarchię Arytmetyczną lub Hierarchię Analityczną. A może (N) P, (N) EXP, 2 (N) EXP, $\ldots$

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

Z drugiej strony książka Harela, Kozen i Tiuryn ​​ma zestaw różnych problemów związanych z kafelkami, które są NP, , i zakończone. Problemy są przydatne do pokazywania redukcji, ale nie jest całkowicie jasne, czy uogólniają się jednolicie, aby objąć inne poziomy hierarchii, w których siedzą. Σ 0 2 Σ 1 $\Pi^0_1$$\Sigma^0_2$$\Sigma^1_1$

Czy ktoś wie o takim zestawie konkretnych, jednolitych problemów obejmujących hierarchię?

EDYCJA: Tylko dla wyjaśnienia, wiem, że 3 hierarchie, które podam, mają przede wszystkim standardowe definicje pod względem siły przemiennego kwantyfikatora. Nie tego szukam. Szukam czegoś innego, na przykład gry na wykresie lub układanki z tilings.

[Opierając się na spostrzeżeniach Kaveha w komentarzach.] Wydaje się mało prawdopodobne, aby ktoś wymyślił rodzinę problemów, która różni się znacznie od ilościowej formuły boolowskiej, bez obalenia analogu PH hipotezy izomorfizmu Bermana-Hartmanisa. Bez tego każdy wymyślony przez ciebie problem byłby nie tylko równoważny , ale w rzeczywistości byłby z nim izomorficzny. Jednym ze sposobów zdefiniowania tutaj izomorfizmu między dwoma językami jest wzięcie pojedynczego języka abstrakcyjnego, ale zakodowanie jego obiektów (w tym przypadku liczbowych formuł boolowskich) przy użyciu dwóch różnych kodowań boolowskich.$QBF_k$

Z drugiej strony izomorfizm niekoniecznie jest dobrym osądem, co jest przydatne dla ludzi, aby wymyślić dowody. Wszakże w hierarchii arytmetycznej twierdzenie o izomorfizmie Myhilla udowadnia arytmetyczny analog hipotezy izomorfizmu BH (w rzeczywistości jest to historia wstecz, ponieważ BH była motywowana przez Myhill). Jednak, jak wskazuje pytanie, istnieje kilka „różnie wyglądających” charakterystyk na różnych poziomach, z których niektóre są bardziej przydatne dla dowodów niż inne.

Chociaż wydaje się mało prawdopodobne, aby ktokolwiek wymyślił taką jednolitą rodzinę języków dla każdego poziomu PH, dwa badania ( jeden , dwa ) Schaefera i Umansa omawiają naturalne problemy, które przynajmniej „wyglądają inaczej” niż QBF dla pierwszych kilku poziomy PH.