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ą. $\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.

cc.complexity-theory computability

— Mark Reitblatt
źródło

Istnieją problemy oparte na grafach (np. Osiągalność) i problemy oparte na logice (ocena obwodu lub wzór pierwszego rzędu). ps: czy próbowałeś stworzyć grę sąsiadującą z dwoma graczami o określonej liczbie rund lub ograniczonej mocy obliczeniowej? przy okazji, może pomóc, jeśli wyjaśnisz, co rozumiesz przez słowa „mundur” i „konkret”.

— Kaveh

Tak, istnieją problemy z wykresem lub obwodem, których zmiany są kompletne dla kilku poziomów. Ale czy potrafisz znaleźć analogi kompletne dla wszystkich poziomów hierarchii? Przez uniform rozumiem, że aby przejść do hierarchii, wystarczy zmienić jakiś parametr w jakiś jednolity sposób. Na przykład zwiększasz liczbę X o jeden, gdzie X jest pewnym parametrem problemu. Mówiąc konkretnie, po prostu nieformalnie mam na myśli dostępne. Nie uważam, że hierarchie problemu zatrzymania są szczególnie dostępne. Z drugiej strony coś takiego jak SAT lub QBF jest bardziej konkretne.

— Mark Reitblatt,

Kontynuując komentarze Kaveha: taki język może być również p-izomorficzny dla TQBF, chyba że ktoś planuje udowodnić, że domniemanie izomorfizmu Bermana-Hartmanisa zawodzi na pewnym (lub każdym) poziomie PH. W tym przypadku byłoby to bardzo cienkie przebranie, ponieważ byłoby to jedynie ponowne kodowanie TQBF, to znaczy zapisałeś skwantyfikowane formuły zdań za pomocą innego kodowania boolowskiego.

— Joshua Grochow

@Mark: Nie mam dobrej intuicji w przypuszczeniu izomorfizmu. Oryginalny artykuł BH sugerował, że może to być prawda; Joseph i Young zasugerowali następnie, że funkcje jednokierunkowe mogą pokazywać, że jest to fałsz (w zasadzie: zastosuj funkcję jednokierunkową do SAT, aby uzyskać kompletny NP, który prawdopodobnie nie jest izomorficzny dla SAT), ale potem Rogers pokazał relatywizowane światy realizujące wszystkie cztery możliwości dotyczące: istnienia funkcji jednokierunkowych i hipotezy izomorfizmu. Nie wiem więc, czy w tej chwili istnieje konsensus. Oto artykuł Rogersa: dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486

— Joshua Grochow

(Artykuł Johna Rogersa wydaje się być około 2 lata później niż dyskusja na blogu CC, ale nie znam dokładnej historii, kiedy uzyskał wynik, w przeciwieństwie do tego, kiedy został opublikowany).

— Joshua Grochow,

[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.

— Joshua Grochow
źródło

Ładne połączenie z BH. :)

— Kaveh