Najbardziej wydajny sposób na konwersję obwodu na obwód (dowolnej głębokości) za pomocą fanout 1 bramki

EDYCJA (22 sierpnia 2011 r.):

Jeszcze bardziej upraszczam pytanie i wyróżniam je. Być może to prostsze pytanie będzie miało łatwą odpowiedź. Przekreślę także wszystkie części pierwotnego pytania, które nie są już istotne. (Podziękowania dla Stasysa Jukny i Ryana O'Donnella za częściową odpowiedź na oryginalne pytanie!)

Tło:

Biorąc pod uwagę obwód AC ⁰ o głębokości k i rozmiarze S, istnieje inny obwód AC ⁰ obliczający tę samą funkcję z głębokością k i rozmiarem tak że nowy obwód ma fanout = 1 dla wszystkich bramek. Innymi słowy, obwód wygląda jak drzewo (z wyjątkiem wejść, ponieważ wejścia mogą zostać rozszerzone na więcej niż jedną bramkę). Jednym ze sposobów jest powielenie wszystkich bramek, które mają Fanout> 1, aż wszystkie bramy będą miały Fanout = 1.$O(S^k)$

Ale czy jest to najbardziej efektywny sposób konwersji obwodów prądu przemiennego ^{0 na} obwody prądu przemiennego ^{0 za} pomocą Fanout 1? Przeczytałem następujące informacje w wykładzie 14 notatek kursowych Ryana O'Donnella :

Czy to oznacza, że ​​istnieje sposób, aby wziąć dowolny obwód k AC ⁰ głębokości k wielkości S i przekształcić go w obwód AC ⁰ z wentylatorem 1, głębokością k i rozmiarem ? Jeśli tak, jak to się robi i czy jest to najbardziej znana metoda? $(2kS)^2$

Oryginalne pytanie:

Biorąc pod uwagę AC ⁰ obwód z głębokości k i rozmiarze S, co jest najlepszym znanym sposobem (w sensie minimalizacji rozmiaru obwodu obwodu wypadkowej) konwersji to do AC ⁰ obwodzie głębokości k i bramy fanout 1? Czy znane są z tego dolne granice?

Nowsze, prostsze pytanie:

To pytanie jest rozluźnieniem pierwotnego, w którym nie nalegam, aby wynikowy obwód miał stałą głębokość. Jak wyjaśniono powyżej, istnieje sposób na przekształcenie obwodu prądu przemiennego ⁰ o głębokości k, rozmiar S w obwód o rozmiarze tak aby nowy obwód miał fanout = 1 dla wszystkich bramek. Czy jest lepsza konstrukcja?$O(S^k)$

Biorąc pod uwagę obwód prądu przemiennego ⁰ o głębokości k i rozmiarze S, jaka jest najbardziej znana metoda (pod względem minimalizacji rozmiaru obwodu powstałego obwodu) przekształcenia go w obwód o dowolnej głębokości z bramkowaniem 1?

Spróbuję podsumować moje poprzednie komentarze.

Zignorujmy najpierw fakt, że twój pierwotny obwód ma (stałą) głębokość ; po prostu założyć, że ma rozmiar S . Niech A będzie najmniejszą liczbą, tak że każdy nieograniczony obwód wachlarzowy S może zostać przekształcony w nieograniczoną formułę wachlarzową F o rozmiarze O ( S A ) . Twierdzę, że najlepszym, co do tej pory możemy zrobić, jest osiągnięcie A = O ( S / log 2 S ) . Powiedzmy, nawet nie wiadomo, czy jakikolwiek obwód (fanin-2) o rozmiarze S = O ( n $k$$S$$A$$S$$F$$O(S^A)$$A=O(S/\log^2 S)$$S=O(n)$można zasymulować za pomocą formuły o rozmiarze mniejszym niż .$\exp(n/\log n)$

Aby pokazać twierdzenie, przekształcamy wzór w wzór Fanin-2 F ' o rozmiarze M = O ( S 2 A ) . Dobrze wiadomo, że głębokość D każdego wzoru F ' może być logarytmiczna w swojej wielkości, to znaczy D = O ( log M ) = O ( A log S ) . [Zostało to po raz pierwszy wykazane przez Chrapczenko 1968, a następnie stała pod big-O została poprawiona do D ≤ 1,73 log 2$F$$F′$$M=O(S^{2A})$$D$$F′$$D=O(\log M)=O(A\log S)$$D\leq 1.73\log_2M$kilku autorów.] Z drugiej strony, najbardziej znany wynik dla Fanin-2 obwodów [Paterson Valianta TCS 2 (3), 397-400], stwierdza, że . Zatem posiadanie symulacji z A znacznie mniejszą niż S / log 2 S poprawiłoby najlepiej znaną symulację głębokości wielkości dla obwodów.$Depth=O(Size/\log Size)$$A$$S/\log^2 S$

Jest to jednak tylko „słowo ostrzeżenia” - nie odpowiada na twoje pytanie, ponieważ zakładasz, że twój pierwotny obwód ma stałą głębokość , co oznacza, że ​​w tym przypadku możemy po prostu przyjąć A = k (lub A = k - 1 jeśli mamy jedną bramę wyjściową). Moc symulacji Paterson-Valiant polega na tym, że ma ona zastosowanie do dowolnych, nawet bardzo niezrównoważonych obwodów, których głębokość jest prawie całej wielkości! Ale w ustawieniu ograniczonej głębokości nawet przypadek k = 3 nie jest jasny: czy każdy obwód o głębokości 3 o rozmiarze S można przekształcić w formułę o głębokości 3 o rozmiarze znacznie mniejszym niż S $k$$A=k$$A=k−1$$k=3$$S$$S^2$? Myślę, że odpowiedź powinna brzmieć „nie” (może być ciekawym ćwiczeniem dla studentów). Formuła głębokości 3 to po prostu duża OR CNF. Pytanie polega na znalezieniu OR dla CNF, które mają wiele wspólnych klauzul, ale poza tym są „bardzo różne”, aby wymusić formułę dużej głębokości-3.

Problem polega na tym, że chcemy uzyskać formułę (obwód fanout-1). Jak wskazano powyżej, zezwolenie na bramy fanout-2 upraszcza symulację: Hoover, Klawe i Pippenger [JACM 31 (1), 1980] pokazują, że każdy obwód fanin-2 wielkości i głębokości D ma równoważne fanin-2 i fanout -2 obwodowy rozmiar 3 S - 2 n i głębokość 2 D . Zatem jeśli fanin jest nieograniczony, wynikowy obwód będzie miał rozmiar O ( S 2 ) i głębokość O ( D log S ) .$S$$D$$3S−2n$$2D$$O(S^2)$$O(D\log S)$

Jest jeszcze jeden wynik w jakiś sposób związany z twoim pytaniem. Lozhkin (1981) udowodnił, że jeśli funkcję boolowską można obliczyć za pomocą wzoru A C 0 o głębokości k i rozmiarze S , to f można obliczyć za pomocą wzoru Fanin-2 o głębokości D ≤ k - 1 + ⌈ log 2 S ⌉ (wynika to z Twierdzenia 6.2 w mojej książce). Zauważ, że trywialna górna granica to tylko D ≤ k log S (gdybyśmy symulowali każdą pojedynczą bramę drzewem logu głębokości S ).$f$$AC^0$ $k$$S$$f$$D\leq k-1+\lceil\log_2S\rceil$$D\leq k\log S$$\log S$