Können wir in der Tiefe

Können wir ein Bit-Schwellwertgatter durch polynomgroße (unbegrenzte Fan-In-) Schaltungen der Tiefe lg n berechnen ?$n$ ? Können wir alternativ die Anzahl der Einsen in den Eingangsbits unter Verwendung dieser Schaltungen zählen?$\frac{\lg n}{\lg \lg n}$

Ist &dgr$\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg \lg n}), O(\lg n))$

Man beachte , dass . Es stellt sich also im Wesentlichen die Frage, ob wir bei der Berechnung von Schwellwertgattern einen Ig Ig n -Faktor in der Tiefe von Schaltkreisen einsparen können .$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$$\lg \lg n$

Bearbeiten:

Wie Kristoffer in seiner Antwort schrieb, können wir einen Faktor einsparen . Aber können wir ein bisschen mehr sparen? Können wir O ersetzen ( lg $\lg \lg n$mito(lg$O(\frac{\lg n}{\lg \lg n})$?$o(\frac{\lg n}{\lg \lg n})$

Es scheint mir, dass der geschichtete Brute-Force-Trick nicht funktioniert, um auch nur zu speichern (im Allgemeinen jede Funktion in lg lg n + ω ( 1 ) ).$2 \lg \lg n$$\lg \lg n + \omega(1)$

$C$$O(\log n)$$C$$O(\log n/\log\log n)$$\log\log n$$2^{\log\log n} = \log n$Tore der letzten Ebene im Block darunter. Wir können also jedes Gate in der letzten Schicht durch eine polynomgroße DNF ersetzen, wobei die Eingänge die Gates in der letzten Schicht des darunter liegenden Blocks sind. Wenn Sie dies für alle Gates in den letzten Schichten für alle Blöcke tun und diese verbinden, sollte sich der gewünschte Schaltkreis ergeben.

$\log n/ \log\log n$