Tiefenreduzierung für Boolesche Schaltungen

9

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 s √ der Tiefe 4 berechnet wirdsd .

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

Mathe-Lernender
quelle
1
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:

9

O(n)O(logn)2O(n/loglogn)

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

Alex Golovnev
quelle
3
ACC0d22polylog(n)polylog(n)