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

42

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:

  • DTIMEHierarchia D T I M E
  • NTIMEHierarchia 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 CNC (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)WAWW
  • Hierarchia liczenia
  • Hierarchia Fouriera
  • Boolean Hierarchy (ponad ), równa również Query Hierarchy (ponad N P )NPNP
  • 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 dBPd(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.

chazisop
źródło
2
To wygląda bardzo podobnie do pytania na Wiki Wiki. Mam to przekonwertować?
Dave Clarke,
Twierdzenie Ladner można uogólnić, aby uzyskać nieskończoną hierarchię między innymi klasami (zakładając, że są one różne), takie jak między P i P ^ # P .
Tyson Williams,
13
Można również wspomnieć o twierdzeniach „antyhierarchicznych”, czyli o dychotomii. Twierdzenia o dychotomii prawdopodobnie mogłyby uzyskać dla siebie całą ankietę, ale prawdopodobnie należy je przynajmniej wymienić obok czegoś takiego jak twierdzenie Ladnera.
Joshua Grochow,
1
Pytasz tylko o hierarchie klas problemów? Istnieje również koncepcja „hierarchii testów”, patrz na przykład arxiv.org/abs/quant-ph/0308032
Alessandro Cosentino,
1
Tak, brane są pod uwagę tylko hierarchie klas złożoności. Nawet ograniczając się do tych, jest bardzo wiele do zebrania informacji.
chazisop

Odpowiedzi:

21

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

Ze złożonego zoo :

FHk jest klasą problemów rozwiązanych przez jednolitą rodzinę wielowymiarowych obwodów kwantowych, przy czympoziomykbramek Hadamarda i wszystkich innych bram zachowują podstawę obliczeniową.

Jest otwarty problem, aby pokazać, że w hierarchii Fouriera jest nieskończona względem wyrocznię (czyli FHk jest dokładnie zawarte w FHk+1 ).

Robin Kothari
źródło
18

- 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 : NN taka, że T I M E [ g ( n ) ] = T I M E [ f ( g ( n ) ) ] .f:NNf(n)=Ω(n)g:NNTIME[g(n)]=TIME[f(g(n))]

g

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

TIME[nk]i.o.TIME[nk1]/(nlogn)

(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 .nknk1nlogn{Mi}nk1nlognM(x)xx=yz|z|=log|x|Mz(x,y)L(M)i.o.TIME[nk1]/(nlogn)

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

Ryan Williams
źródło
2
Czy to ? w przeciwnym razie stwierdzenie nie jest interesujące: wystarczy wybrać . g ( n ) = nTIME[g(n)]=TIME[f(g(n))]g(n)=n
Sasho Nikolov
@Sasho, wydaje się, że tak. Stwierdzenie twierdzenia o luce Borodina (poprzez link) mówi tyle samo.
Daniel Apon,
16

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.

  • C0P=P
  • C1P=PP
  • Ck+1P=PPCkP

Następnie, jeśli chodzi o hierarchię wielomianową, jest zdefiniowane jako .CHkCkP

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

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

Bruno
źródło
16

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

Również w ECCC .

Yonatan
źródło
tutaj pokazano, że większość właściwości wymaga zapytań w modelu kwantowym. Można to podłączyć do dowodu twierdzenia o hierarchii odpowiedzi, aby pokazać, że ma ona zastosowanie również do kwantowego testowania właściwości. (W rzeczywistości dla każdego naturalnego modelu obliczeniowego z co najmniej jedną właściwością wymagającą przetestowania zapytań , a dla każdego obliczalnego masz właściwości, które można przetestować w zapytania). Ω(n)Ω(g(n))f(n)O(g(n))Θ(f(n))
Artem Kaznatcheev
15

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:AC0d+1d

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

Joshua Grochow
źródło
11

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

Tyson Williams
źródło
10

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.

Marcos Villagra
źródło
10

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.

Ktoś
źródło
9

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ą.DNPLDP

xLy1,yn<poly(|x|): P(x,y1,,yn)=0.
DNP

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

i1, ΣiDΣiPΣi+1D
Alexander Knop
źródło
D jest zdefiniowane w drugim („Złożoność diofantyny”).
GMB
@ AndrásSalamon Linki nie wydają się działać.
8

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 .

András Salamon
źródło
8

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

  • A hierarchia
  • AW hierarchia
  • EW hierarchia
  • LOG hierarchia
  • M hierarchia
  • S hierarchia
  • W -hierarchia
  • Wfunc -hierarchia

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

Martin Lackner
źródło
5

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{0,1}ijL[i,j]L[i,j]

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

Σ2Π2L

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

L

obrotami
źródło
4

GiPHCPC

Sji

Kaveh
źródło
4

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

CFLCFLCFL

Marcos Villagra
źródło
3

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.

Klemens C.
źródło
Wskaźnik do tej odpowiedzi , która koncentruje się na pierwszej (GoldreichKNR09).
Clement C.
3

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.
mum
źródło
2

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

Tayfun Pay
źródło
1

cc

Denis Pankratov
źródło
Dzięki za dodanie, zredagowałem twój komentarz, aby wyjaśnić, że koNP odnosi się do złożoności komunikacji (wiem, że jest to często pomijane w społeczności złożoności komunikacji, aby uniknąć bałaganu notacji).
chazisop
0

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 .

Max Kubierschky
źródło