die -Hierarchie zusammen?

12

Wissen wir, dass die -Hierarchie nicht zusammenbricht ( für alle d )?TC0TCd0TCd+10d

Der Zoo-Eintrag für TC0 erwähnt nur die Trennung zwischen Tiefe 2 und 3.

Gibt es auch eine Standardreferenz für die Tatsache, dass die \ mathsf {AC ^ 0_d}ACd0 -Hierarchie nicht zusammenbricht?

Kaveh
quelle
1
Eine verwandte Frage wäre, wie viele verschiedene Funktionen es in / . Eine angemessene Untergrenze für diese Mengen würde Ihre Fragen beantworten. Auch ein Beweis der Enge für Hastads Umschalt-Lemma würde vielleicht Ihre zweite Frage beantworten. T C 0 dACd0TCd0
MCH
4
Für die zweite Frage glaube ich, dass sie erstmals in Sipsers STOC '83-Veröffentlichung "Borel-Mengen und Schaltungskomplexität" bewiesen wurde . Dies ergibt jedoch nur Superpolynom-Untergrenzen. Die ersten exponentiellen Untergrenzen wurden von Yao gegeben, später von Håstad verbessert.
Robin Kothari
@MCH, wolltest du ? Oder meinst du die Anzahl der Äquivalenzklassen von Problemen in wrt Reduktionen? T C 0 d A C 0 dTCd0/ACd0TCd0ACd0
Kaveh
2
Was ich meine ist sehr einfach: Wie viele verschiedene Funktionen kann die Klasse von Kreisen der Größe darstellen? (Wir können die Anzahl der Schaltkreise sehr einfach abschätzen, aber wir sollten darauf achten, dass einige von ihnen dieselbe Funktion berechnen.) Sobald Sie zeigen, dass diese Größe mit wächst , sind Sie fertig. s dACd0sd
MCH
2
@ Dilworth, ungleichmäßig. Das Zählen scheint nicht zu funktionieren, ansonsten könnten wir, wie ich weiter unten bemerkte, von das geöffnet ist. N C 1TC0NC1
Kaveh

Antworten:

15

Wir kennen keine guten unteren Schranken (dh eine superpolynomiale untere Schranke für eine Sprache in ) für Schwellwertschaltungen der Tiefe 2 (unbegrenzte Gewichte). Tiefen-3-Schaltkreise, die aus Mehrheitsgattern aufgebaut sind, dh T C 0 3, enthalten diese Klasse, und daher kennen wir auch für diese Klasse keine guten Untergrenzen.NEXPTC30

Kristoffer Arnsfelt Hansen
quelle
Dies beantwortet meine Frage. Vielen Dank Kristoffer.
Kaveh
Wie ich im Kommentar schrieb oben, auch wenn ein Problem in nexp nicht außerhalb TC bekannt seine 0 2 , ist es nicht immer noch möglich , dass die uneinheitliche TC 0 Hierarchie ist die richtige über eine Zählargument untere Schranke? 200
Dilworth
Darf ich auch fragen, inwiefern dies mit den bekannten exponentiellen Untergrenzen von TC 0 2 und der im Komplexitätszoo berichteten Trennung von Schwellwertschaltungen für Tiefe 3 und Tiefe 2 vereinbar ist? Vermisse ich etwas? 20
Dilworth
1
@ Dilworth, ich denke, das liegt daran, dass es mit Mehrheit nicht Schwelle definiert wird.
Kaveh
Hmm .. was meinst du genau? Hängt das mit der Notiz von Kristoffer über "unbegrenzte Gewichte" zusammen?
Dilworth
12

Wenn ich keinen Fehler mache, scheint es mindestens so schwierig zu sein , zu beweisen, dass die -Hierarchie nicht zusammenbricht, wie N C 1 von T C 0 zu trennen :TCd0NC1TC0

Lassen Sie uns die Boolesche Formel Auswertung Problem bezeichnen . B F E ist für N C 1 unter A C 0 -Reduktionen vollständig .BFEBFENC1AC0

BFENC1AC20

NC1=TC0BFETCd0dNC1TCd+20TC0TCd+20

d

TC0TCd0NC1TCd+20BFETCd0

Kaveh
quelle