die -Hierarchie zusammen?

Wissen wir, dass die -Hierarchie nicht zusammenbricht ( für alle )? $\mathsf{TC^0}$ $\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ $d$

Der Zoo-Eintrag für $\mathsf{TC^0}$ erwähnt nur die Trennung zwischen Tiefe 2 und 3.

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

cc.complexity-theory reference-request complexity-classes circuit-complexity bounded-depth Kaveh
quelle

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.

A C_{d}^{0}

$AC_d^0$

T C_{d}^{0}

$TC_d^0$

MCH

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_{d}^{0} / A C_{d}^{0}

$\mathsf{TC^0_d}/\mathsf{AC^0_d}$

T C_{d}^{0}

$\mathsf{TC^0_d}$

A C_{d}^{0}

$\mathsf{AC^0_d}$

Kaveh

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.

A C_{d}^{0}

$AC_d^0$

s

$s$

d

$d$

MCH

@ Dilworth, ungleichmäßig. Das Zählen scheint nicht zu funktionieren, ansonsten könnten wir, wie ich weiter unten bemerkte, von das geöffnet ist.

T C^{0}

$\mathsf{TC^0}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Antworten:

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 enthalten diese Klasse, und daher kennen wir auch für diese Klasse keine guten Untergrenzen. $\mathsf{NEXP}$ $\mathsf{TC}^0_3$

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

, ist es nicht immer noch möglich , dass die uneinheitliche TC

Hierarchie ist die richtige über eine Zählargument untere Schranke?

_{2}^{0}

$^0_2$

^{0}

$^0$

Dilworth

Darf ich auch fragen, inwiefern dies mit den bekannten exponentiellen Untergrenzen von TC

und der im Komplexitätszoo berichteten Trennung von Schwellwertschaltungen für Tiefe 3 und Tiefe 2 vereinbar ist? Vermisse ich etwas?

_{2}^{0}

$_2^0$

Dilworth

@ 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

Wenn ich keinen Fehler mache, scheint es mindestens so schwierig zu sein , zu beweisen, dass die -Hierarchie nicht zusammenbricht, wie von trennen : $\mathsf{TC^0_d}$ $\mathsf{NC^1}$ $\mathsf{TC^0}$

Lassen Sie uns die Boolesche Formel Auswertung Problem bezeichnen . ist für unter -Reduktionen vollständig . $BFE$ $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0}$

$BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0_2}$

$\mathsf{NC^1}=\mathsf{TC^0}$ $BFE \in \mathsf{TC^0_d}$ $d$ $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$ $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$

$d$

$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ $BFE \notin \mathsf{TC^0_d}$

Kaveh
quelle