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


18

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 0 o głębokości k i rozmiarze S, istnieje inny obwód AC 0 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(Sk)

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 :

Załóżmy, że C jest dowolnym obwodem głębokości k o rozmiarze S, który oblicza parzystość. Jest to ćwiczenie pokazujące, że C można przekształcić w poziomowany obwód o głębokości k, w którym poziomy zmieniają się na bramkach AND i OR, przewody wejściowe są literałami 2n, a każda bramka ma rozwinięcie 1 (tj. Jest to drzewo ) - a rozmiar wzrasta do co najwyżej .(2kS)2O(S4)

Przypis: W rzeczywistości jest to nieco trudne zadanie. Łatwiej jest, jeśli musisz uzyskać tylko rozmiar , który jest prawie taki sam dla naszych celów, jeśli myślisz o k jako „stałej”.O(Sk)

Czy to oznacza, że ​​istnieje sposób, aby wziąć dowolny obwód k AC 0 głębokości k wielkości S i przekształcić go w obwód AC 0 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 0 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 0 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 0 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(Sk)

Biorąc pod uwagę obwód prądu przemiennego 0 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?


5
Ograniczenie jest w porządku. Ale jeśli ograniczenie ( 2 k S ) 2 zachowa się dla dowolnych obwodów (nie tylko tych obliczających funkcję parzystości), wówczas można symulować każdy obwód fanin-2 wielkości S przez fanin- 2 formuła wielkości O ( S 5 ) : S bramki fanin-2 wystarczą do symulacji jednej bramki niezwiązanego fanina. Następnie formułę można przekształcić w jedną z głębokości O ( log S )O(Sk)(2kS)2SO(S5)SO(logS)(dobrze znany wynik, błędnie przypisany do Spiry). W ten sposób uzyskalibyśmy, że głębokość obwodu jest najbardziej . Ale to zbyt miłe, aby mogło być prawdziwe: najbardziej znaną górną granicą głębokości obwodu jest tylko O ( S / log S ) . O(logS)O(S/logS)
Stasys,

2
Btw rzeczywiście obowiązuje także dla dowolnych obwodów, ale tylko wtedy, gdy pozwolimy na wrota fanin-2 (patrz np. Thm. 4.1 w książce Wegenera); wtedy obwody nadal pamiętają wyniki pośrednie. Sytuacja z fanin-1 jest zupełnie inna: tutaj obwody w ogóle nie mają pamięci. Ale pytanie Robina jest bardzo interesujące. Interesujące byłoby nawet wykazanie, że obwody o głębokości 3 wielkości S można symulować za pomocą wzorów o głębokości 3 wielkości mniejszych niż S 2 . O(kS)2)SS2
Stasys,

4
Ufałbym temu, co Staś powie powyżej; W tych notatkach nie byłem bardzo ostrożny (przepraszam). Z drugiej strony, pamiętam, gdy ich pisania jest bardzo sfrustrowany o zaopatrywaniu fakt - o którym mowa w wielu, wielu gazetach, ale prawie nigdy z cytatu - że można konwertować dowolne C 0 układów warstwowych do nich bez wysadzania rozmiar „dużo” . Bardzo chciałbym zobaczyć wskaźnik do najlepiej znanego wyniku na ten temat. AC0
Ryan O'Donnell,

2
@Ryan O'Donnell: rzeczywiście, można łatwo układ warstwowy z wytryskowe . Używamy asocjatywności, aby osiągnąć, że każda bramka AND ma tylko bramki OR jako dane wejściowe i na odwrót; głębokość pozostaje niezmieniona. Następnie ułóż bramy według ich głębokości i dodaj w razie potrzeby trywialne wrota fanin-1 OR i AND, aby uzyskać obwód warstwowy; głębokość pozostaje taka sama, a rozmiar zwiększa się tylko o współczynnik k. Ale zrozumiałem, że Robin chce, aby obwód został przekształcony w formułę (obwód podobny do drzewa, z tym wyjątkiem, że literały wejściowe mogą mieć duże rozwinięcie). O(kS)
Stasys

2
@Ryan O'Donnell: Dziękujemy za odpowiedź i za przesłanie notatek z wykładów online! W szczególności notatki z wykładu na temat analizy funkcji boolowskich były bardzo pomocne.
Robin Kothari,

Odpowiedzi:


11

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 )kSASFO(SA)A=O(S/log2S)S=O(n)można zasymulować za pomocą formuły o rozmiarze mniejszym niż .exp(n/logn)

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 MFFM=O(S2A)DFD=O(logM)=O(AlogS)D1.73log2Mkilku 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/logSize)AS/log2S.

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 2kA=kA=k1k=3SS2? 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 ) .SD3S2n2DO(S2)O(DlogS)

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 ).fAC0 kSfDk1+log2SDklogSlogS

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.