Minimalna szerokość drzewa obwodu dla WIĘKSZOŚCI

Jaka jest minimalna szerokość drzewa obwodu powyżej $\{\wedge,\vee,\neg\}$ do obliczenia MAJ?

Tutaj MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to $1$ .

Dbam tylko o rozmiar obwodu (powinien być wielomianowy) i że dane wejściowe powinny być odczytywane tylko raz, chociaż rozwarcie bramki wejściowej może być dowolne (ma to decydujący wpływ na szerokość drzewa obwodu - rozgałęzienie programy otrzymane z twierdzeniem Barrington jest od MAJ $\in$ $\mathsf{NC}^1$ , interpretowane jako obwody skośnych, nie pomagają). I oczywiście szerokość drzewa jest najważniejsza. Ja nie dbają o głębokości lub innego parametru.

Niektóre z typowych obwodów dla MAJ obejmują:

Obwody Wallace drzewa (egTheorem 8,9 tutaj ), które wykorzystują podstęp 3-do-2, aby umieścić MAJ w $\mathsf{NC}^1$ ?
Obwody monotoniczne Valianta $\mathsf{NC}^1$ dla MAJ (np. Twierdzenie 4 tutaj )
$\log^{O(1)}{n}$ sieć sortująca głębokość, taka jaksortowanieBatchera
Sieć sortująca AKS

Czy któryś z nich ma ograniczoną lub nawet polilogarytmiczną szerokość drzewa?

Lub w rzeczywistości

Czy istnieją powody, by sądzić, że dla MAJ nie ma obwodów o ograniczonej szerokości drzewa?

Zauważ, że każda funkcja obliczana przez drzewa ograniczonej szerokości obwodu mogą być obliczane przez obwodzie nawet gdy nie jest odczytywany jednokrotnego zastrzeżeniem poprzez JansenSarma . Zatem niewiarygodność takiej rodziny obwodów wskazywałoby, że granica ta może być jeszcze bardziej zacieśniona w przypadku obwodów jednokierunkowych. $\mathsf{NC}^1$

— SamiD
źródło

Dlaczego nie jest to trywialne dla żadnego języka

? O ile widzę, formuły (tj. Drzewa) mają szerokość drzewa

, czy coś mi brakuje?

{N C}^{1}

$\mathrm{NC}^1$

1

$1$

— Emil Jeřábek

Myślę, że OP identyfikuje wszystkie liście drzewa formuły, które odpowiadają tej samej zmiennej, która tworzy cykle.

— Sasho Nikolov

Obwód dla większości może być zaimplementowany w linii O (log n). Obwód po prostu symuluje algorytm online, który odczytuje jeden bit wejściowy na raz i dodaje 1 do liczby za pomocą bitów O (log n) tylko wtedy, gdy wejście ma wartość 1. Zauważ, że głębokość obwodu wynosi O (n). Zobacz Ryc. 1 ( arxiv.org/pdf/1404.5565v1.pdf ). Obwód o małej głębokości niekoniecznie ma małą szerokość, ponieważ jak zauważył Sasho Nikolov, musisz zidentyfikować węzły odpowiadające tej samej zmiennej wejściowej.

— Mateus de Oliveira Oliveira,

@MateusdeOliveiraOliveira Konstrukcja, którą wskazałeś, jest ładna i prosta i jest prawie tym, czego potrzebuję. To, czego naprawdę potrzebuję, to konstrukcja działająca na ograniczonej szerokości drzewa (lub jakieś wskazanie, dlaczego nie jest to możliwe). Poczekam kilka dni, aby zobaczyć, czy jest jakaś inna odpowiedź - w przeciwnym razie (jeśli przekształcisz swój komentarz w odpowiedź) zatwierdzę go.

— SamiD

@SamiD Rozszerzyłem ten komentarz na odpowiedź. Nie pisałem wcześniej jako odpowiedzi, ponieważ jest to tylko połowa tego, o co prosiłeś.

— Mateus de Oliveira Oliveira

Odpowiedzi:

Odpowiadając na połowę pytania Samira.

Niech są DAG i dwa podzbiory wierzchołków . Oznaczamy przez zbiór wszystkich krawędzi w z jednym punktem końcowym w i drugim punktem końcowym w . Jeśli $G=(V,E)$ $V_1,V_2\subseteq V$ $G$ $E(V_1,V_2)$ $G$ $V_1$ $V_2$ $\omega = (v_1,...,v_n)$ $G$

o w (G, ω) = max_{i} | E ({v_{1}, . . ., v_{i}}, {v_{i + 1}, . . ., v_{n}} |

$\mathbf{ow}(G,\omega) = \max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$

ω

$\omega$

G

$G$

o w (G) = min_{ω} o w (G, ω),

$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$

G

$G$

G

$G$

c w (G)

$\mathbf{cw}(G)$

G

$G$ , niezależnie od tego, czy uporządkowanie jest topologiczne, czy nie. Mamy następującą sekwencję nierówności: gdzie i są odpowiednio pathwidth i treewidth z .

t w (G) \leq p w (G) \leq c w (G) \leq o w (G),

$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$

p w (G)

$\mathbf{pw}(G)$

t w (G)

$\mathbf{tw}(G)$

G

$G$

Twierdzimy, że WIELKOŚĆ bitów może być obliczona w -szerokości , a zatem w szerokości . Obwód symuluje algorytm online, który odczytuje jeden bit wejściowy na raz i dodaje do licznika za pomocą bitów wtedy i tylko wtedy, gdy . Na początku licznik jest inicjowany na $n$ $O(\log n)$ $O(\log n)$ $b$ $b$ $O(\log n)$ $b=1$ $0$ . Na koniec obwód akceptuje wtedy i tylko wtedy, gdy wartość licznika jest większa niż n / 2. Łatwo zauważyć, że bramki obwodu ADD, który dodaje jeden do rejestru licznika, można uporządkować topologicznie w taki sposób, że ma on stałą szerokość online, ponieważ obwody te muszą po prostu realizować operację kontynuacji. Cały obwód jest sekwencją obwodów gdzie wyjście jest podłączone do wejścia , a wyjście jest podłączone do wejście COMP. Teraz, jeśli topologicznie uporządkujemy całkowity obwód w taki sposób, że wszystkie bramki pojawią się przed bramami i wszystkimi bramkami $C=(ADD_1,ADD_2,...,ADD_n,COMP)$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ $C$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ pojawia się przed bramkami COMP, wówczas ta kolejność topologiczna ma szerokość online . Konstrukcja ta jest zilustrowana na rycinie 1 mojego papieru, aby pokazać, że wzmocnienie prawdopodobieństwa można wykonać w logarytmicznej szerokości online. $O(\log n)$

Obs: Głębokość obwodu C wynosi . $O(n)$

— Mateus de Oliveira Oliveira
źródło

Na marginesie, robienie tego samego obwodu, ale jako binarne drzewo (z wyjściem na root), a nie ścieżka daje obwodu z treewidth O (log n) i głębokość O (log n)

— Daniello

Wydaje się, że bezpośrednie tłumaczenie na drzewa dałoby głębokość O ((log n) ^ 2), ponieważ potrzebowalibyśmy głębokości O (log n) dla każdego sumatora. Ale prawdą jest, że szerokość będzie wynosić O (log n).

— Mateus de Oliveira Oliveira

Oczywiście masz rację, dzięki! Wydaje się, że jeśli dodatki zostaną zaimplementowane jako DNF, to otrzymamy szerokość i głębokość O (log n), ale rozmiar .

O (n^{3})

$O(n^3)$

— daniello

rzeczą w reprezentowaniu sumatora jako DNF jest to, że może potencjalnie zwiększyć szerokość, ponieważ teraz każda zmienna będzie współdzielona (na pierwszy rzut oka wielomianowo) z wieloma klauzulami. Twoja sugestia zmniejszenia głębokości do O (log n) zadziałałaby, gdybyś mógł wykazać, że dodanie dwóch liczb za pomocą bitów O (log n) można wykonać na stałej głębokości i logarytmicznej szerokości.

— Mateus de Oliveira Oliveira

Cóż - dla każdej funkcji logicznej w bitów wejściowych i bitów Wyjście DNF ma głębokość , rozmiar , a treewidth ponieważ usuwanie Gates wejście + wyjście pozostawia niezależnego zestawu ...

a

$a$

b

$b$

2

$2$

2^{a} + a + b

$2^a + a + b$

\leq a + b

$\leq a+b$

— daniello,

Odpowiadając na drugą połowę pytania - oto szkic próbny dla dolnej granicy szerokości dla pewnej stałej . Granica jest niezależna od wielkości lub dowolnego innego aspektu obwodu. W pozostałej części argumentu jest obwód, to szerokość a to liczba bramek wejściowych. $c \cdot \log n$ $c$ $C$ $t$ $C$ $n$

Pierwszym krokiem jest użycie zrównoważonego lematu separatora do wykresów ograniczonej szerokości . Bramy (w tym bramki wejściowe) obwodu można podzielić na trzy części , i , tak że a zarówno jak i zawierają co najmniejbramy wejściowe i między i nie ma łuków (drutów) . $L$ $R$ $S$ $|S| \leq t+1$ $L$ $R$ $n/3-|S|$ $L$ $R$

W pozostałej części dowodu jedyną właściwością obwodu, której będziemy używać, jest podział na partycje - więc dowód faktycznie daje dolną granicę wielkości zrównoważonego separatora jak powyżej. $S$

Mając na rękę zbudować obwód z , jak następuje: do każdej bramki w wykonać dwa kolejne bramy i i dokonać i paszy w . Dla wszystkich drutów prowadzących do od zamiast tego przejść do . Dla wszystkich drutów prowadzących do od zamiast tego przejść do . Niech $(L,S,R)$ $C'$ $C$ $g$ $S$ $g_L$ $g_R$ $g_L$ $g_R$ $g$ $g$ $L$ $g_L$ $g$ $R$ $g_R$

S^{'} = {g, g_{L}, g_{R} : g \in S} .

$S' = \{g, g_L, g_R : g \in S\}.$

Dla każdego z przypisań do utwórz obwód, który wyprowadza 1, jeżeli (a) przypisanie do bramek wejściowych powoduje, że wyjście prawdziwe, a (b) przypisanie do bramek wejściowych ustawia wszystkie wartości bramy jak się domyślam. Wywołaj te obwody , , dla . Zauważ, że obwód naturalnie rozpada się na dwa i tak, że zależy tylko od bram wejściowych , zależy tylko od bram wejściowych $2^{|S'|}$ $S'$ $C'$ $S'$ $C_1$ $C_2$ $C_3 \ldots C_x$ $x \leq 8^t$ $C_i$ $C_i^L$ $C_i^R$ $C_i^L$ $L \cup S'$ $C_i^R$ $R \cup S'$ i dla każdego przyporządkowania do bram wejściowych mamy tę . $C_i = C_i^L \wedge C_i^R$

Ponieważ każde przypisanie do bram wejściowych jest zgodne z pewnym przypuszczeniem, co dzieje się w , mamy . Mamy więc ponownie napisany Obwód jako OR (z Fanin I) i na (z Fanin ), gdzie i numer bramy jest podawany na wyjście i odpowiednio. $S'$ $C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$ $C$ $8^t$ $2$ $i$ $C_i^L$ $C_i^R$

Niech będzie zbiorem najwyższych bramek AND. Najpierw udowodnimy, że. Daje to prostą dolną granicę . Udowodnimy wtedy lepszą więź. $Z$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$ $t$

Załóżmy, żeI przejąć wlog że zawiera mniej bramek wejściowych niż . Zatem zarówno jak i zawierają co najmniejbramy wejściowe. Zgodnie z zasadą gołębnika istnieją dwie różne liczby i tak że istnieją dwa różne przypisania do bramek wejściowych , jedna, która ustawia gates na prawdę, jedna, która ustawia , tak, że obwody , wszystkie to samo. Ale istnieje przypisanie do bram wejściowych w $2^{|Z|} < n/3-|S|$ $L$ $R$ $L$ $R$ $n/3-|S|$ $i$ $j$ $L$ $i$ $j$ $C_1^L$ $C_2^L \ldots C_x^L$ $R$ tak, że MAJORITY wyprowadza FAŁSZ, jeśli bramki w są ustawione na true, a MAJORITY wyprowadza PRAWDA, jeśli bramki w są ustawione na true. To jest sprzeczność, a więc co sugeruje, że szerokość wynosi co najmniej . $i$ $L$ $j$ $L$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$

Teraz pokazujemy lepszą granicę:. Załóżmy wlog że zawiera mniej bramek wejściowych niż . Zatem zarówno L, jak i R zawierają co najmniejbramy wejściowe. Rozważmy „fałszywe” przypisanie do . Niech będzie najmniejszą liczbą bramek wejściowych które muszą być ustawione na true, tak aby MAJ wyprowadzał PRAWDA, biorąc pod uwagę, że wszystkie jest ustawione na fałsz. $|Z| \geq n/3-|S|$ $L$ $R$ $n/3-|S|$ $L$ $r$ $R$ $L$

Ponieważ ustawienie na fałszywe i dokładnie wejściowe bramy do TRUE marki większościowych nie musi być pewne w taki sposób, wyjść TRUE wlog to . Wszystkie przypisania do z bramkami wejściowymi mniejszymi niż true muszą ustawić na false. Ponieważ ustawienie bramki wejściowej na true i bramek wejściowych na true powoduje, że wyjście MAJORITY , ustawienie bramki na true musi powodować co najmniej jedną $L$ $r$ $R$ $1$ $i$ $C_i^L$ $C_1^L$ $R$ $r$ $C_1^R$ $1$ $L$ $r-1$ $R$ $1$ $1$ $L$ $C_i^L$ outpur true dla . wlog możemy założyć . Następnie wszystkie przypisania do które ustawiają co najwyżej bramki wejściowe na true, muszą ustawić na false, i tak dalej - możemy powtórzyć ten argument razy. Ale to oznacza, że, dając dolną granicę dla . $i \neq 1$ $i=2$ $R$ $r-2$ $C_2^R$ $r$ $|Z| \geq r \geq n/3-|S|$ $c \cdot \log n$ $t$

[Zdaję sobie sprawę, że ten szkic jest nieco falowany w niektórych miejscach, zapytaj, czy coś jest niejasne ...]

— Daniello
źródło