Welche Hierarchien und / oder Hierarchiesätze kennen Sie?

Ich schreibe gerade eine Umfrage zu Hierarchietheoremen über TCS. Auf der Suche nach verwandten Arbeiten habe ich festgestellt, dass Hierarchie nicht nur in FHM und Mathematik, sondern in zahlreichen Wissenschaften, von Theologie und Soziologie bis Biologie und Chemie, ein grundlegendes Konzept ist. Angesichts der Fülle an Informationen hoffe ich, dass ich diese Community um Hilfe bitten kann. Natürlich möchte ich nicht, dass Sie eine bibliografische Suche für mich durchführen, sondern ich bitte Sie um zwei Arten von Informationen:

1. Hierarchien und Hierarchietheoreme, die das Ergebnis Ihrer Arbeit oder der Arbeit Ihrer Kollegen oder anderer Personen sind, mit denen Sie vertraut sind und die Ihrer Meinung nach nicht so bekannt sind. Dies kann beispielsweise ein Hierarchietheorem für ein undurchsichtiges Rechenmodell sein, an dem Sie interessiert sind, oder eine Hierarchie bestimmter Klassen, z. B. im Zusammenhang mit der Spieltheorie.

2. Hierarchien und Hierarchietheoreme, die Sie für unbedingt erforderlich halten, um in eine solche Umfrage einbezogen zu werden. Dies wäre mir wahrscheinlich bereits bekannt, aber es wäre hilfreich zu sehen, welche Hierarchien Sie für wichtiger halten und warum. Dies könnte die von der Art sein „halte ich sehr wichtig , denn ohne sie wären wir nicht in der Lage sein , diese Art von Forschung zu tun“ oder „Obwohl es nicht so gut bekannt ist , in Logik-basierte TCS verwenden wir ständig diese Hierarchie und mich halte es für ein wichtiges Werkzeug. " . Und ja, ich glaube, dass Menschen aus der Logik viele Hierarchien zu erwähnen haben, bedenken Sie jedoch, dass es sich um Hierarchien von Problemen handelt.$PH$

Ich werde hier eine aktualisierte Liste führen:

• Hierarchie$DTIME$
• Hierarchie$NTIME$
• Hierarchie$SPACE$
• Arithmetische Hierarchie (auch als Kleene bekannt)
• Hyperarithmetische Hierarchie
• Analytische Hierarchie
• Chomsky-Hierarchie
• Grzegorczyk-Hierarchie und die verwandten: Wainer-Hierarchie (schnell wachsend), Hardy-Hierarchie
  (langsam wachsend) und Veblen-Hierarchie
• Ritchies Hierarchie
• Hierarchie von Axt (wie in Axt63 definiert )

• Die Schleifenhierarchie (definiert in MR67 )

• ( A C , A C C ) Hierarchie $NC$$AC$$ACC$

• Die Tiefenhierarchie , wie in Sipser83 definiert
• Polynom Hierarchy ( ) und die weniger raffinierte Meyer-Stockmeyer - Hierarchie (kein dinstinction zwischen quantifiers)$PH$
• Exponentielle Hierarchie ( )$ELEMENTARY$

• Zwischenhierarchie (Ladner-Theorem) $NP$

• Der nicht ganz so robuste (Arthur-Merlin)$AM$

• Die (Nichtdeterministische festen Parameter) Hierarchie und der damit verbundene Alternating W Hierarchie ( A W -hierarchy) und W * -hierarchy (W mit Parameter-Dependent Depth)$W$$AW$$W^{*}$
• Hierarchie zählen
• Fourier-Hierarchie
• Boolesche Hierarchie (über ), auch gleich der Abfragehierarchie (über N P )$NP$$NP$
• Hierarchien zum Testen von Eigenschaften, wie in GoldreichKNR09 dargestellt
• Die Punkttiefenhierarchie sternloser regulärer Sprachen
• : Die durch Verzweigungsprogramme für polynomielle Größen lösbaren Klassen bilden mit der zusätzlichen Bedingung, dass jedes Bit der Eingabe höchstens d Mal getestet wird, eine Hierarchie für verschiedene Werte von$BP_{d}(P)$$d$
• Die Zeithierarchie für die Schaltungskomplexität
• Die Polynomhierarchie in der Kommunikationskomplexität

Hinweis: Wenn Sie nicht exklusiv erwähnt werden möchten, sagen Sie dies bitte. Als Faustregel erwähne ich sowohl die Community als auch die spezifische Person, die neue Informationen ans Licht bringt.

Die Fourier-Hierarchie im Sinne von " Yaoyun Shi, Quantum und klassische Kompromisse ".

Aus dem Komplexitätszoo :

$\mathsf{FH}_k$ ist die Klasse von Problemen, die durch eine einheitliche Familie von Quantenschaltungen polynomialer Größe lösbar sind, wobei$k$Niveaus von Hadamard-Gattern und allen anderen Gattern die Berechnungsbasis bewahren.

• $\mathsf{FH}_0 = \mathsf{P}$
• $\mathsf{FH}_1 = \mathsf{BPP}$
• $\mathsf{FH}_2$ enthält Factoring aufgrund desPhasenschätzungsalgorithmusvonKitaev.

Es ist ein offenes Problem zu zeigen, dass die Fourier-Hierarchie in Bezug auf ein Orakel unendlich ist (dh, $\mathsf{FH}_k$ ist streng in $\mathsf{FH}_{k+1}$ ).

- In Anlehnung an "Anti-Hierarchien" könnte Borodins Lückentheorem erwähnenswert sein.

$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$

- Es gibt auch interessante Verstärkungen der üblichen Zeithierarchien, wie zum Beispiel:

(es gibt Probleme in der Zeit nicht erfolgreich durch jederzeit gelöst werden Zeitmaschine unter Verwendung Bits der Beratung, selbst für nur auf unendlich viele Eingangslängen). Der Beweis ist einfach: Lassen Sie die Zeitmaschinen , die Ratschläge als zweite Eingabe annehmen . Definiere das in wobei, führt und gibt die entgegengesetzte Antwort aus. Dann ist .$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)$

- Das Fehlen bekannter Zeithierarchien in bestimmten Situationen sollte berücksichtigt werden (als offene Probleme). zum Beispiel ?${\sf BPTIME}[n] = {\sf BPP}$

Der Komplexitäts-Zoo enthält einige Hierarchien . Unter ihnen wurden die Zählhierarchie und die Boolesche Hierarchie nicht bereits zitiert.

[EDIT] Um meine Antwort informativer zu gestalten, eine schnelle Definition der Zählhierarchie.

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

Dann wird für die als .$\sf CH$$\bigcup_k {\sf C_kP}$

Die Zählhierarchie wurde von Wagner [Wag86] definiert. Zusammenhänge zur Theorie der Schwellwertschaltungen wurden von Allender & Wagner [AW93] entdeckt. In jüngerer Zeit verwendete Bürgisser [Bür09] auch die Zählhierarchie, um das Modell von Valiant mit der Vermutung von Shub und Smale in Beziehung zu setzen . Insbesondere hat er bewiesen, dass die Vermutung eine Superpolynom-Untergrenze für die bleibende Karte impliziert.$\tau$$\tau$

[Wag86] KW Wagner. Die Komplexität kombinatorischer Probleme mit prägnanter Eingabedarstellung . Acta Mathematica 23 (3), 325-356, 1986.
[AW93] E. Allender & KW Wagner. Zählen von Hierarchien: Polynomzeit- und Konstanttiefenschaltungen . Current Trends in Computer Science , 469-483, 1993.
[Bür09] P. Bürgisser. Über die Definition von Ganzzahlen und den Nachweis der arithmetischen Schaltung unterer Schranke . Computational Complexity 18 (1), 81-103, 2009.

Goldreich et. al. haben Hierarchiesätze für Eigenschaftstests:

• Oded Goldreich, Michael Krivelevich, Ilan Newman und Eyal Rozenberg: Hierarchietheoreme für Eigenschaftstests. Property Testing , Vorlesungsskripte in Computer Science, Vol. 6390, S. 289–294, Springer, 2010.

Auch auf der ECCC .

Sipser zeigte eine Tiefenhierarchie innerhalb von , dh , dass Schaltkreise mit der Tiefe der Polygröße leistungsfähiger sind als Schaltkreise mit der Tiefe der Polygröße:$AC^0$$d+1$$d$

Sipser, M. Borel setzt und Schaltungskomplexität . STOC 1983.

Dieter van Melkebeek und Mitautoren haben Zeit- und Raumhierarchien für semantische Modelle mit Rat, einschließlich Randomisierung.

• Dieter van Melkebeek, Konstantin Pervyshev: Eine allgemeine Zeithierarchie mit einem Ratschlag . Computational Complexity 16 (2): 139-179 (2007)
• Jeff Kinne, Dieter van Melkebeek: Raumhierarchieergebnisse für randomisierte und andere semantische Modelle . Computational Complexity 19 (3): 423-475 (2010)

Hier finden Sie weitere Hierarchien für semantische Klassen mit Hinweisen. Insbesondere für ZPTIME und RTIME.

Lance Fortnow, Rahul Santhanam und Luca Trevisan. Hierarchien für semantische Klassen . In STOC'05.

Es gibt die Zheng-Weihrauch-Hierarchie für reelle Zahlen

X. Zheng und K. Weihrauch. Die arithmetische Hierarchie reeller Zahlen . Mathematische Logik Quarterly.Vol. 47 (2001), Nr. 1, 51–65.

Es gibt eine Klasse , die in einem von L. Adelman und K. Manders aus dem Jahr 1975 definiert wurde und ein diophantinisches Analogon der Klasse . Eine Sprache ist in wenn ein Polynom so dass Ob gleich ist, ist ein offenes Problem. Diese Gleichheit würde Zusammenhänge zwischen Zahlentheorie und Informatik aufzeigen.$\mathsf{D}$$\mathsf{NP}$$L$$\mathsf{D}$$P$

Es gibt ein Diophantin-Analogon der Polynom-Hierarchie, die "Diophantin-Hierarchie". Die polynomischen und diophantinen Hierarchien sind miteinander verflochten:

Eine andere strenge Hierarchie: Verzweigungsprogramme, die jedes Bit nur eine begrenzte Anzahl von Malen testen. Je mehr Tests zulässig sind, desto größer ist die Klasse der Verzweigungsprogramme. Normalerweise sind die Verzweigungsprogramme auch auf die Polynomgröße beschränkt. BP _d (P) ist die Klasse von Verzweigungsprogrammen für die Polynomgröße, die jedes Bit bis zu mal testen können .$d$

L / poly ist die Vereinigung von BP _d (P) über alles d , während BP _d-1 (P) BP _d (P) für jedes d ist .$\subsetneq$

In der parametrisierten Komplexitätstheorie gibt es mehrere Hierarchien, obwohl in Veröffentlichungen häufig nur die bereits erwähnte -Hierarchie vorkommt. Andere sind:$\mathsf{W}$

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

Sie sind alle in Parametrized Complexity Theory, Flum and Grohe, Birkhäuser, 2006, beschrieben .

Ich bin nicht sicher, ob dies Ihren Kriterien entspricht, aber es gibt die Punkttiefenhierarchie der sternlosen regulären Sprachen.

Die Hierarchie für die Schaltkreisgröße finden Sie in der vorherigen Frage .

Die Theorie der regulären Sprachen unendlicher Bäume hat zu mehreren Hierarchien geführt, die derzeit untersucht werden, wobei viele Fragen noch offen sind.

Bei der Verwendung von Automaten für unendliche Bäume ist die Paritätsbedingung (oder Mostowski-Bedingung) von besonderem Interesse, da nicht deterministische Paritätsautomaten alle regulären Sprachen unendlicher Bäume ausdrücken können und die Struktur der Akzeptanzbedingung einfacher ist als bei anderen wie Rabin oder Müller .

Jeder Paritätsautomat hat einen Rang in dem und die Struktur der Akzeptanzbedingung beschreiben. Wenn also eine Sprache durch einen (det / ND / alt) Automaten vom Rang erkennbar ist, sagen wir, dass zum -Level von (bzw.) gehört:$[i,j]$$i\in\{0,1\}$$i\leq j$$L$$[i,j]$$L$$[i,j]$

• deterministische Mostowski-Hierarchie (nicht alle regulären Sprachen)
• nichtdeterministische Mostowski-Hierarchie
• alternierende Mostowski-Hierarchie

Das Level der alternierenden Hierarchie (dh ist sowohl Büchi als auch Co-Büchi definierbar) entspricht dem schwachen Level und ist gekennzeichnet durch schwache alternierende Automaten, die sich zu einer Hierarchie entwickeln:$\Sigma_2\cap \Pi_2$$L$

• schwache Indexhierarchie (nicht alle regulären Sprachen)

Für alle diese Hierarchien (mit Ausnahme der deterministischen) ist die Entscheidbarkeit der Zugehörigkeit zu einer Ebene für eine bestimmte reguläre Sprache ein offenes Problem. Die Verknüpfungen zwischen diesen Hierarchien und topologischen Klassifikationen (auch als Wadge-Hierarchie und Borel-Hierarchie bezeichnet) warfen auch mehrere offene Probleme auf. Beispielsweise wird vermutet, dass die schwache Indexhierarchie und die Borel-Hierarchie zusammenfallen. Alle diese Hierarchien sind bekanntermaßen streng, und einige Sonderfälle bei der Entscheidung des Niveaus (insbesondere bei niedrigen Niveaus oder mit einem eingabedeterministischen Automaten) wurden kürzlich gelöst.$L$

Es gibt Hierarchien in der Komplexität von Aussagenbeweisen, die denen in der Komplexität von Schaltkreisen ähnlich sind. Beispiel: Propositional-Dachsysteme ähneln , C-Frege-Proof-Systeme für ähneln den Schaltungskomplexitätsklassen usw.$G_i$$\mathsf{PH}$$C \subset \mathsf{P}$$C$

Es gibt auch Hierarchien in der beschränkten Arithmetik, zB -Theorien usw.$\mathsf{S^i_j}$

Hier ist eine neue Hierarchie für kontextfreie Sprachen von Tomoyuki Yamakami.

Er führt einen Orakelmechanismus in nichtdeterministischen Pushdown-Automaten und Begriffen von Turing und Vielfachreduzierbarkeit ein. Dann wird eine neue Hierarchie für kontextfreie Sprachen (Context-free languages, CFL) ähnlich der Polynom-Hierarchie erstellt. Zum Beispiel , usw. Der interessante Teil von alledem ist, dass ein Zusammenbruch in der CFL-Hierarchie nur dann auftritt, wenn die Polynom-Hierarchie zusammenbricht.$CFL$$CFL^{CFL}$

Auf einen der vom OP (GoldreichKNR09) genannten Stichpunkte eingehen: Es gibt verschiedene Hierarchietheoreme bei Eigenschaftstests und Näherungsnachweisen, die sich auf die Abfragekomplexität, die Adaptivität oder die Testbarkeit in Bezug auf die Anzahl der Runden beziehen (für Beweise von Nähe). Siehe zB

• Hierarchietheoreme für Eigenschaftstests , Oded Goldreich, Michael KrivelevichIlan Newman und Eyal Rozenberg, 2012. https://link.springer.com/article/10.1007/s00037-011-0022-4 [vom OP erwähnt]
• Ein Hierarchiesatz für interaktive Näherungsbeweise , Tom Gur und Ron Rothblum, 2017. http://drops.dagstuhl.de/opus/volltexte/2017/8153/
• Hierarchiesätze zum Testen von Eigenschaften in größenunabhängiger Abfragekomplexität , Oded Goldreich, 2018. https://eccc.weizmann.ac.il/report/2018/098/
• Ein Adaptivitätshierarchiesatz für Eigenschaftstests , Clément Canonne und Tom Gur, 2018. https://link.springer.com/article/10.1007%2Fs00037-018-0168-4

Durch diese Frage bei cs.stackexchange wurde mir die Gattungshierarchie regulärer Sprachen bewusst . Grundsätzlich können Sie reguläre Sprachen anhand der minimalen Gattungsoberfläche charakterisieren, in die das Diagramm ihres DFA eingebettet sein kann. In [1] wird gezeigt, dass es Sprachen beliebig großer Gattungen gibt und dass diese Hierarchie korrekt ist.

1. Bonfante, Guillaume und Florian Deloup. " Die Gattung der regulären Sprachen. " Mathematical Structures in Computer Science 28.1 (2018): 14-44.

Counting Polynomial Hierarchy, kurz #PH. Die erste Ebene ist #P, dann #NP ... usw.

Die Polynomialhierarchie in der Komplexität der Kommunikation nach Babai, Frankl und Simon (siehe Originalarbeit hier und ohne Paywall hier ). Die Bedeutung dieser Hierarchie ist schwer zu überschätzen. Zuallererst wurde die Disjunktitätsfunktion von BFS in derselben Veröffentlichung eingeführt, in der die Hierarchie eingeführt wurde, und die Disjunktität erschien ganz natürlich als ein coNP -vollständiges Problem. Wie Sie wissen, ist die Disjunktheit DIE Funktion in der Kommunikationskomplexität. Zweitens ist der Nachweis der unteren Schranken gegen die Polynomhierarchie in der Kommunikationskomplexität ein großes offenes Problem mit wichtigen Auswirkungen auf andere Bereiche des TCS (siehe z. B. diesen Aufsatz und die darin enthaltenen Referenzen).$^{cc}$

Betrachten Sie die eindeutige Polynom-Hierarchie, Referenz hier , Originalreferenz hier für die eindeutige Polynom-Hierarchie (paywalled). Während wir uns mit der Booleschen Hierarchie BH und Klassen wie , die gute Ergebnisse in Bezug auf das Schließen haben, und Unterschiede festlegen, können wir Zusammenhänge zu eindeutigen Berechnungen untersuchen. $D_{p}$

Wie die Autoren (in der ursprünglichen Referenz) angeben, liefern die Klassen und Ergebnisse, die sich auf und beziehen . Mit einer eindeutigen Schaltung könnten sie unterschiedlich charakterisieren . Im Zusammenhang mit der obigen Hierarchie steht auch die Versprechen-eindeutige Hierarchie. Lowness-Ergebnisse für die eindeutige Polynom-Hierarchie - "Wenn für ein spärlicher Turing Completer festgelegt ist , wird die Hierarchie auf niedrigere Ebenen oder in den eindeutigen Fall Promise reduziert". $NC^{k}$$AC^{k}$$P$$PSPACE$$P$$UP$

Zur weiteren Untersuchung von Booleschen Konnektiven und des Graphisomorphismus werden die Niedrigen und Hohen Hierarchien herangezogen , die ebenfalls auf Wikipedia verweisen .

Mehr auf der dunklen Seite: Mein Heirarchiesatz zweiter Ordnung für Fixpunktlogiken in der Finiten Modelltheorie. Siehe noch einen anderen Hierarchiesatz .