Jakie znasz hierarchie i / lub twierdzenia dotyczące hierarchii?

Obecnie piszę ankietę na temat twierdzeń hierarchicznych dotyczących TCS. Szukając powiązanych artykułów zauważyłem, że hierarchia jest fundamentalną koncepcją nie tylko w TCS i matematyce, ale w wielu naukach, od teologii i socjologii po biologię i chemię. Widząc, że ilość informacji jest ogromna, mam nadzieję, że mógłbym poprosić o pomoc tę społeczność. Oczywiście nie chcę, żebyś przeprowadzał dla mnie wyszukiwanie bibliograficzne, ale proszę o dwa rodzaje informacji:

1. Hierarchie i twierdzenia dotyczące hierarchii, które są wynikiem twojej pracy lub pracy twoich kolegów lub innych osób, które znasz i które uważasz, że nie są tak dobrze znane. Może to być na przykład twierdzenie o hierarchii dla niejasnego modelu obliczeniowego, którym jesteś zainteresowany, lub hierarchia określonych klas, np. Związanych z teorią gier.

2. Hierarchie i twierdzenia dotyczące hierarchii, które uważasz za absolutnie konieczne, powinny zostać uwzględnione w tego rodzaju ankiecie. Prawdopodobnie byłoby mi to już znane, ale dobrze byłoby zobaczyć, jakie hierarchie uważasz za ważniejsze i dlaczego. Może to być tego rodzaju „Uważam, że $PH$ bardzo ważne, ponieważ bez niej nie bylibyśmy w stanie przeprowadzić tego rodzaju badań” lub „Chociaż nie jest to tak dobrze znane, w opartych na logice TCS stale używamy tej hierarchii, a ja uważają to za ważne narzędzie ”. . I tak, wierzę, że ludzie z logiki mają wiele hierarchii do wspomnienia, jednak pamiętajmy, że mówimy o hierarchiach problemów.

Będę przechowywać aktualną listę tutaj:

• $DTIME$Hierarchia D T I M E
• $NTIME$Hierarchia N T I M E
• $SPACE$ Hierarchia
• Hierarchia arytmetyczna (znana również jako Kleene)
• Hierarchia hiperarytmiczna
• Hierarchia analityczna
• Hierarchia Chomsky'ego
• Hierarchia Grzegorczyk i pokrewne: Hierarchia Wainera (szybko rosnąca), Hierarchia twarda
  (wolno rosnąca) i hierarchia Veblena
• Hierarchia Ritchie
• Hierarchia Axta (zgodnie z definicją w Axt63 )

• Hierarchia pętli (zdefiniowana w MR67 )

• Hierarchia N $NC$ ($AC$ ,$ACC$ )

• Hierarchia głębokości, zgodnie z definicją w Sipser83
• Hierarchia wielomianowa ( ) i mniej dopracowana hierarchia Meyera-Stockmeyera (brak rozróżnienia między kwantyfikatorami)$PH$
• Hierarchia wykładnicza ( )$ELEMENTARY$

• Hierarchia pośrednia (twierdzenie Ladnera) $NP$

• Niezbyt solidny (Arthur-Merlin)$AM$

• (niedeterministycznych stałej Parameter) hierarchii i podobne przemienny W hierarchii ( W -hierarchy) i W * -hierarchy (W z parametrów zależnych od G)$W$$AW$$W^{*}$
• Hierarchia liczenia
• Hierarchia Fouriera
• Boolean Hierarchy (ponad ), równa również Query Hierarchy (ponad N P )$NP$$NP$
• Hierarchie do testowania właściwości, jak widać w GoldreichKNR09
• Hierarchia głębokości kropek w zwykłych językach bez gwiazd
• : Klasy rozwiązywalne przez programy do rozgałęziania wielomianów, z dodatkowym warunkiem, że każdy bit danych wejściowych jest testowany co najwyżej d razy, tworzą hierarchię dla różnych wartości$BP_{d}(P)$$d$
• Hierarchia czasu złożoności obwodu
• Hierarchia wielomianowa w złożoności komunikacji

Uwaga: jeśli nie chcesz być wymieniony wyłącznie, powiedz to. Jako ogólną zasadę wspomnę zarówno społeczność, jak i konkretną osobę, która ujawnia nowe informacje.

Hierarchia Fouriera zdefiniowana w „ Yaoyun Shi, kwant i klasyczne kompromisy ”.

Ze złożonego zoo :

$\mathsf{FH}_k$ jest klasą problemów rozwiązanych przez jednolitą rodzinę wielowymiarowych obwodów kwantowych, przy czympoziomy$k$bramek Hadamarda i wszystkich innych bram zachowują podstawę obliczeniową.

• $\mathsf{FH}_0 = \mathsf{P}$
• $\mathsf{FH}_1 = \mathsf{BPP}$
• $\mathsf{FH}_2$ zawiera faktoring ze względuna algorytm szacowania faz Kitaeva.

Jest otwarty problem, aby pokazać, że w hierarchii Fouriera jest nieskończona względem wyrocznię (czyli $\mathsf{FH}_k$ jest dokładnie zawarte w $\mathsf{FH}_{k+1}$ ).

- Wzdłuż linii „antyhierarchii” warto wspomnieć o twierdzeniu Borodina .

Twierdzenie. Dla każdej całkowitej obliczalnej funkcji takiej, że f ( n ) = Ω ( n ) , istnieje całkowita obliczalna g : N → N taka, że T I M E [ g ( n ) ] = T I M E [ f ( g ( n ) ) ] .$f : {\mathbb N} \rightarrow {\mathbb N}$$f(n) = \Omega(n)$$g : {\mathbb N} \rightarrow {\mathbb N}$${\sf TIME}[g(n)] = {\sf TIME}[f(g(n))]$

$g$

- Istnieją również interesujące wzmocnienia zwykłych hierarchii czasowych, takie jak:

(istnieją problemy w czasie których nie można pomyślnie rozwiązać za pomocą maszyny czasu używającej porad, nawet dla nieskończenie wielu długości wejściowych). Dowód jest prosty: pozwól czasu , które przyjmują kawałków porady jako drugiego wejścia. Zdefiniuj który dzieli na gdzie, uruchamia i wyświetla odpowiedź przeciwną. Następnie .$n^k$$n^{k-1}$$n-\log n$$\{M_i\}$$n^{k-1}$$n-\log n$$M'(x)$$x$$x=yz$$|z|=\log |x|$$M_z(x,y)$$L(M') \notin i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$

- Należy wziąć pod uwagę brak znanych hierarchii czasu w niektórych sytuacjach (jako problemy otwarte). Na przykład, czy ?${\sf BPTIME}[n] = {\sf BPP}$

Złożoność Zoo daje pewne hierarchie . Wśród nich nie wymieniono jeszcze hierarchii liczenia i hierarchii boolowskiej.

[EDYCJA] Aby moja odpowiedź była bardziej informacyjna, szybka definicja Hierarchii Liczenia.

• ${\sf C_0P} = {\sf P}$
• ${\sf C_1P} = {\sf PP}$
• ${\sf C_{k+1}P} = {\sf PP^{C_kP}}$

Następnie, jeśli chodzi o hierarchię wielomianową, jest zdefiniowane jako .$\sf CH$$\bigcup_k {\sf C_kP}$

Hierarchia liczenia została zdefiniowana przez Wagnera [Wag86]. Odnośniki do teorii obwodów progowych odkryli Allender i Wagner [AW93]. Znacznie później Bürgisser [Bür09] zastosował także hierarchię zliczania, aby powiązać model Valianta z hipotezą Shau i Smale'a . W szczególności udowodnił, że hipoteza implikuje superskładnikową dolną granicę stałej.$\tau$$\tau$

[Wag86] KW Wagner. Złożoność problemów kombinatorycznych z zwięzłą reprezentacją danych wejściowych . Acta Mathematica 23 (3), 325-356, 1986.
[AW93] E. Allender i KW Wagner. Hierarchie liczenia: obwody wielomianowe i obwody o stałej głębokości . Aktualne trendy w informatyce , 469–483, 1993.
[Bür09] P. Bürgisser. Po zdefiniowaniu liczb całkowitych i udowodnieniu dolnej granicy obwodu arytmetycznego . Złożoność obliczeniowa 18 (1), 81-103, 2009.

Goldreich i in. glin. mają twierdzenia o hierarchii do testowania właściwości:

• Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Testing Property. Testy nieruchomości , wykłady z informatyki, t. 6390, s. 289–294, Springer, 2010.

Również w ECCC .

Sipser pokazał hierarchię głębokości w obrębie , to znaczy, że obwody głębokości o wielkości poli są silniejsze niż obwody głębokości o wielkości poli:$AC^0$$d+1$$d$

Zestawy Sipser, M. Borel i złożoność obwodów . STOC 1983.

Dieter van Melkebeek i współautorzy dysponują hierarchiami czasu i przestrzeni dla modeli semantycznych z poradami, w tym randomizacją.

• Dieter van Melkebeek, Konstantin Pervyshev: Ogólna hierarchia czasu z jedną radą . Złożoność obliczeniowa 16 (2): 139-179 (2007)
• Jeff Kinne, Dieter van Melkebeek: Wyniki hierarchii kosmicznej dla randomizowanych i innych modeli semantycznych . Złożoność obliczeniowa 19 (3): 423–475 (2010)

Oto więcej hierarchii dla klas semantycznych z poradami. W szczególności dla ZPTIME i RTIME.

Lance Fortnow, Rahul Santhanam, Luca Trevisan. Hierarchie dla klas semantycznych . W STOC'05.

Istnieje hierarchia Zheng-Weihrauch dla liczb rzeczywistych

X. Zheng i K. Weihrauch. Hierarchia arytmetyczna liczb rzeczywistych . Kwartalna logika matematyczna. Vol. 47 (2001), nr 1 51–65.

Istnieje klasa , zdefiniowana w artykule z 1975 r. Przez L. Adelmana i K. Mandersa, który jest diofantycznym analogiem klasy . Język jest zawarty w iff istnieje wielomian taki, że Czy równa się jest otwartym problemem. Ta równość pokazałaby związki między teorią liczb a informatyką.$\mathsf{D}$$\mathsf{NP}$$L$$\mathsf{D}$$P$

Istnieje diofantyczny analog wielomianowej hierarchii, zwany „hierarchią diofantyczną”. Hierarchie wielomianowa i diofantyczna są ze sobą powiązane:

Kolejna ścisła hierarchia: programy rozgałęziające, które testują każdy bit tylko ograniczoną liczbę razy. Im więcej testów jest dozwolonych, tym większa jest klasa programów rozgałęziających. Zwykle programy rozgałęziające są również ograniczone do wielkości wielomianowej. BP _d (P) to klasa programów do rozgałęziania wielomianów, które mogą testować każdy bit do razy.$d$

L / poli jest związek BP _D (P) na całej d , podczas gdy BP _D-1 (p) BP _d (p) dla każdego d .$\subsetneq$

W sparametryzowanej teorii złożoności istnieje kilka hierarchii, chociaż tylko wspomniana już hierarchia pojawia się często w publikacjach. Inni są:$\mathsf{W}$

• $\mathsf{A}$ hierarchia
• $\mathsf{AW}$ hierarchia
• $\mathsf{EW}$ hierarchia
• $\mathsf{LOG}$ hierarchia
• $\mathsf{M}$ hierarchia
• $\mathsf{S}$ hierarchia
• $\mathsf{W^∗}$ -hierarchia
• $\mathsf{W^{func}}$ -hierarchia

Wszystkie zostały opisane w Sparametryzowanej teorii złożoności, Flum and Grohe, Birkhäuser, 2006 .

Nie jestem pewien, czy to pasuje do twoich kryteriów, ale istnieje hierarchia głębokości kropek w zwykłych językach bez gwiazd.

Hierarchia wielkości obwodu, patrz poprzednie pytanie .

Teoria zwykłych języków nieskończonych drzew zrodziła kilka hierarchii, które są obecnie badane, z wieloma otwartymi pytaniami.

Podczas korzystania z automatów na drzewach nieskończonych, warunek parzystości (lub warunek Mostowskiego) jest szczególnie interesujący, ponieważ niedeterministyczne automaty parzystości mogą wyrażać wszystkie regularne języki drzew nieskończonych, a struktura warunku akceptacji jest prostsza niż w innych, takich jak Rabin lub Müller .

$[i,j]$$i\in\{0,1\}$$i\leq j$$L$$[i,j]$$L$$[i,j]$

• deterministyczna hierarchia Mostowskiego (nie wszystkie zwykłe języki)
• niedeterministyczna hierarchia Mostowskiego
• naprzemienna hierarchia Mostowskiego

$\Sigma_2\cap \Pi_2$$L$

• słaba hierarchia indeksów (nie wszystkie zwykłe języki)

$L$

$G_i$$\mathsf{PH}$$C \subset \mathsf{P}$$C$

$\mathsf{S^i_j}$

Oto nowa hierarchia języków bezkontekstowych autorstwa Tomoyuki Yamakami.

$CFL$$CFL^{CFL}$

Opracowanie jednego z punktów wypunktowanych przez OP (GoldreichKNR09): istnieje kilka twierdzeń hierarchicznych w testowaniu właściwości i dowodach bliskości, dotyczących złożoności zapytań, adaptacyjności lub testowalności w odniesieniu do liczby rund (dla dowodów potwierdzających bliskość). Zobacz np.

• Twierdzenia dotyczące hierarchii testowania własności , Oded Goldreich, Michael Krivelevich Ilan Newman i Eyal Rozenberg, 2012. https://link.springer.com/article/10.1007/s00037-011-0022-4 [wspomniane przez PO]
• Twierdzenie o hierarchii dla interaktywnych dowodów bliskości , Tom Gur i Ron Rothblum, 2017. http://drops.dagstuhl.de/opus/volltexte/2017/8153/
• Twierdzenia dotyczące hierarchii testowania właściwości w złożoności zapytań nieświadomych wielkości , Oded Goldreich, 2018. https://eccc.weizmann.ac.il/report/2018/098/
• Twierdzenie o hierarchii adaptacji do testowania właściwości , Clément Canonne i Tom Gur, 2018. https://link.springer.com/article/10.1007%2Fs00037-018-0168-4

Z tego pytania na temat cs.stackexchange dowiedziałem się o hierarchii rodzajów zwykłych języków . Zasadniczo można scharakteryzować zwykłe języki na podstawie minimalnej powierzchni rodzaju, w której może zostać osadzony wykres ich DFA. Wykazano w [1], że istnieją języki arbitralnie dużego rodzaju i że ta hierarchia jest właściwa.

1. Bonfante, Guillaume i Florian Deloup. „ Rodzaj języków zwykłych. ” Struktury matematyczne w informatyce 28.1 (2018): 14-44.

Zliczanie hierarchii wielomianowej, w skrócie #PH. Pierwszy poziom to #P, a następnie #NP ... itd.

$^{cc}$

$D_{p}$

$NC^{k}$$AC^{k}$$P$$PSPACE$$P$$UP$

Powiązane z dalszymi badaniami łączników boolowskich i wykresu Izomorfizm to Niska i Wysoka Hierarchia , również odniesienia do Wikipedii .

Więcej na temat niejasnej strony: Moje twierdzenie o heirarchii drugiego rzędu dla logiki stałego punktu w teorii modeli skończonych. Zobacz jeszcze inne twierdzenie o hierarchii .