Czy dodawanie można przeprowadzić na głębokości mniejszej niż 5?

Stosując algorytm przenoszenia patrzeć w przyszłość możemy obliczyć dodatek za pomocą wielomianu głębokość rozmiar 5 (lub 4?) rodzinę obwodu. Czy można zmniejszyć głębokość? Czy możemy obliczyć dodanie dwóch liczb binarnych przy użyciu wielomianowej rodziny obwodów o głębokości mniejszej niż uzyskana za pomocą algorytmu carry look forward? $AC^0$

Czy są jakieś super wielomianowe dolne granice dla wielkości rodzin obwodów $AC^0_d$ obliczających dodatek, gdzie wynosi 2 lub 3? $d$

Przez głębokość rozumiem głębokość przemienną.

cc.complexity-theory circuit-complexity lower-bounds upper-bounds Anonimowy
źródło

Czy możesz nam powiedzieć, jak się nazywasz? Kim jesteś? Przez ostatni miesiąc ludzie tworzyli tutaj nową nazwę użytkownika, zadawali pytania, a następnie usuwali tę nazwę użytkownika!

Tayfun Zapłać

@Geekster, generalnie ludzie nie są zobowiązani do zakładania konta ani używania ich prawdziwych nazwisk (jednak zaleca się to robić z różnych powodów). Jeśli masz ogólne obawy dotyczące czegoś, skorzystaj z Meta teoretycznej w celu podniesienia tego.

Kaveh

Może to być brutalnie wymuszone przez sprawdzenie, że żaden obwód AC

głębokości-

nie może obliczyć

-bitowej sumy dwóch

bitowych wejść dla niektórych stałych

; istnieje tylko skończona liczba funkcji boolowskich bitów wejściowych, które mogą pojawić się na każdej głębokości.

4

$4$

^{0}

$^{0}$

(m + 1)

$(m+1)$

m

$m$

m

$m$

mjqxxxx,

@mjqxxxx: Jak wymusić ograniczenie wielkości wielomianowej w obwodach AC0 podczas brutalnego wymuszania dla ustalonego m? @ OP: Czy obecnie najlepsza głębokość obwodu 4 lub głębokość 5?

Robin Kothari,

@mjqxxxx: Każda funkcja boolowska jest obliczalna na podstawie obwodów głębokości

. Teraz załóżmy, że można znaleźć dla swojej stałej

obwodzie rozmiar

. Jak oceniasz, czy dla każdego

istnieją obwody o rozmiarze

, gdzie

, czy też są tylko obwody o rozmiarze

, gdzie

? Po prostu nie ma możliwości wnioskowania o asymptotycznych informacjach na podstawie skończonego przykładu.

2

$2$

m

$m$

s

$s$

c n

$cn$

n

$n$

c = s / m

$c=s/m$

2^{ϵ n}

$2^{\epsilon n}$

ϵ = (\log s) / m

$\epsilon=(\log s)/m$

Emil Jeřábek wspiera Monikę

Odpowiedzi:

Zgodnie z Twierdzeniem 3.1 w Alexis Maciel i Denis Therien Obwody progowe o małej większości-głębokości istnieje rzeczywiście obwód o głębokości-3 do obliczania dodania dwóch liczb.

Dokładna związany jest gdzie problemy, które mają głębokość-2 obwodów z obu bramy w górę, a obwody obwody o głębokości pierwszej (szczegółowe wyjaśnienie notacji znajduje się w artykule). $\Delta_2 \cdot \mathsf{NC}^0_1$ $\Delta_2 = \Sigma_2 \cap \Pi_2$ $\mathsf{AC}^0$ $\vee,\wedge$ $\mathsf{NC}^0_1$ $\mathsf{NC}^0$

Głównymi pomysłami na dowód są:

Najpierw wyraż obwód Carry-lookahead jako $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Następne, uruchom właściwości zamykający napisać to jako $\Delta_2$ $\Delta_2\cdot\mathsf{NC}^0$
Na koniec skorzystaj z faktu (udowodnionego również w pracy), że $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$

SamiD
źródło

Obwody o głębokości 2 wymagają wielkości wykładniczej do obliczenia sumy, ponieważ obwód o głębokości 2 musi mieć wartość DNF lub CNF i łatwo jest zweryfikować, że istnieje wykładniczo wiele mintermów i maksimów.

Ostrzeżenie : część poniżej jest wadliwa . Zobacz komentarze pod odpowiedzią.

Sposobem liczę to dodanie może być wykonywane w głębi 3. Załóżmy, że a są TH bity dwóch liczb, gdzie jest współczynnikiem LSB i MSB. $a_i$ $b_i$ $i$ $0$ $n$

Obliczmy ty kawałek sumy, w standardowy sposób z perspektywą przenoszenia: $i$ $s_i$

s_{i} = a_{i} \oplus b_{i} \oplus c_{i}

$s_i = a_i \oplus b_i \oplus c_i$

gdzie oznacza XOR, a jest przeniesieniem obliczonym jako: $\oplus$ $c_i$

c_{i} = \underset{j ∣ j < i}{⋁} (g_{j} \land p_{j})

$c_i = \bigvee_{j\mid j < i} (g_j \wedge p_j)$

i oznacza, że ta lokalizacja „wygenerowała” przeniesienie: $g_j$ $j$

g_{j} = (a_{j} \land b_{j})

$g_j = (a_j \wedge b_j)$

a oznacza, że przeniesienie jest propagowane z do : $p_j$ $j$ $i$

p_{j} = \underset{k ∣ j < k < i}{⋀} (a_{j} \lor b_{j})

$p_j = \bigwedge_{k\mid j < k < i} (a_j \vee b_j)$

Licząc głębokość, jest głębokością 2, a jest głębokością 3. Chociaż wydaje się, że jest głębokością 4 lub 5, to tak naprawdę jest to tylko głębokość 3, ponieważ jest to ograniczone przez Fanina obliczenie obwodów głębokości 3, więc jeden może zepchnąć dwa górne poziomy w dół za pomocą formuł de-Morgana, jednocześnie zwiększając rozmiar obwodu o wielomian. $p_j$ $c_i$ $s_i$

Noam
źródło

Nie bardzo rozumiem, jak ograniczone obliczenia Fanin obwodów głębokości 3 są automatycznie głębokością 3. Jeśli, powiedzmy, piszesz

jako

, możesz zrobić pierwszy rozłączenie obwodu o głębokości 3 z

na górze, a drugi rozłączenie obwodu o głębokości 3 z

s_{i}

$s_i$

(c_{i} \land \neg (a_{i} \oplus b_{i})) \lor (\neg c_{i} \land (a_{i} \oplus b_{i}))

$(c_i\land\neg(a_i\oplus b_i))\lor(\neg c_i\land(a_i\oplus b_i))$

⋁

$\bigvee$

⋀

$\bigwedge$ na szczycie. Nie widzę, jak przesunąć górne rozłączenie w dół bez zwiększania głębokości o jeden, aby uwzględnić rozbieżność między typami połączeń w dwóch częściach. Można temu zaradzić, zauważając, że

można również obliczyć w inny sposób za pomocą obwodu o głębokości 3 ...

c_{i}

$c_i$

Emil Jeřábek obsługuje Monikę

... z

na górze. Z drugiej strony wszystkie obwody na głębokości 3 ograniczały dolne wachlowanie, więc nazwałbym je głębokością 2 1/2.

⋀

$\bigwedge$

Emil Jeřábek wspiera Monikę

To oczywiste. Zwracam uwagę na to, że jak napisano, nie ma tutaj OR dwóch obwodów

głębokości z AND na górze. Masz OR z dwóch obwodów

głębokości , z których jeden ma AND na górze, a drugi ma OR na górze. Wątpię, czy takie obwody można ogólnie przekształcić na głębokość

. Pomyśl o wielomianowych wentylatorach AND i OR jako kwantyfikatorach. Możesz wyrazić

d

$d$

d

$d$

d

$d$

jako formuła prenex zblokami kwantyfikatora

, ale potrzebujeszbloków

aby wyrazić ...

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\forall x_{1} \exists x_{2} \dots Q x_{d} ψ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\forall x_1\exists x_2\dots Qx_d\psi(x_1,\dots,x_d))$

d

$d$

d + 1

$d+1$

Emil Jeřábek obsługuje Monikę

... wzór

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\exists x_{1} \forall x_{2} \dots \bar{Q} x_{d} ϕ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\exists x_1\forall x_2\dots \overline Qx_d\phi(x_1,\dots,x_d))$

Emil Jeřábek wspiera Monikę

For an explicit counterexample to the general principle, let

f_{n} (x_{1}, \dots, x_{n})

$f_n(x_1,\dots,x_n)$ be a family of functions computable by

A C_{d}^{0}

$AC^0_d$ circuits with OR on the top requiring super-polynomial depth

d

$d$ circuits with AND on the top (e.g., Sipser functions). Then

x_{0} \oplus f_{n}

$x_0\oplus f_n$ do not have

A C_{d}^{0}

$AC^0_d$ circuits. Assume for contradiction that

C_{n} (x_{0}, \dots, x_{n})

$C_n(x_0,\dots,x_n)$ are such circuits, and that

C_{n}

$C_n$ has OR on the top (the other case is symmetric). By setting

x_{0} = 1

$x_0=1$ , we obtain

A C_{d}^{0}

$AC^0_d$ circuits for

\neg f_{n}

$\neg f_n$ with OR on the top, hence

A C_{d}^{0}

$AC^0_d$ circuits for

f_{n}

$f_n$ with AND on the top, a contradiction.

Emil Jeřábek supports Monica