Tiefenreduzierung für Boolesche Schaltungen

Dieses Ergebnis von Tavenas, Koiran und anderen zeigt, dass jedes Polynom, das von einer Schaltung der Größe $s$ berechnet wird, von einer homogenen Schaltung der Größe Tiefe 4 berechnet wird $s^{\sqrt{d}}$ .

Gibt es ähnliche Ergebnisse für Boolesche Schaltungen oder wissen wir, warum so etwas nicht möglich ist?

cc.complexity-theory circuit-complexity arithmetic-circuits Mathe-Lernender
quelle

Wenn ich mich richtig erinnere, ist ein solches Ergebnis in der booleschen Welt nicht möglich. Ich habe Probleme, mich an das spezifische Ergebnis zu erinnern. Ich denke, das ist es, was arxiv.org/abs/1504.03398 in diese Richtung zeigt. Ich kann dies zu einer Antwort aktualisieren, wenn ich die tatsächliche Referenz finde, an die ich mich vage erinnere.

Chazisop

Antworten:

$O(n)$ $O(\log{n})$ $2^{O(n/\log\log{n})}$

Beachten Sie, dass die Anzahl der Gates in einer Schaltung der Tiefe 3, die eine Zufallsfunktion berechnet, $\Theta(2^{n/2})$ ( Dančík ; Sergeev ) beträgt , während die beste Untergrenze, die wir beweisen können, nur beträgt $2^{\Omega(\sqrt{n})}$ (Håstad;Håstad, Jukna, Pudlák;Paturi, Pudlák, Zane;Boppana;Paturi, Pudlák, Saks, Zane;Meir, Wigderson).

Alex Golovnev
quelle

{A C C}^{0}

$\mathsf{ACC}^0$

d

$d$

2

$2$

2^{p o l y l o g (n)}

$2^{polylog(n)}$

p o l y l o g (n)

$polylog(n)$