Jak mały może być warstwowy obwód logiczna dla funkcji z złożoność obwodu ?

Rozważ funkcję obliczoną przez obwód logiczny z wejściami o rozmiarze na podstawie (z indegree 2 dla bram ). $f$ $C$ $n$ $s(n) = \mathsf{poly}(n)$ $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ $\mathsf{XOR},\mathsf{AND}$

Obwód boolowski jest warstwowy, jeśli można go ułożyć w warstwy ( jest głębokością obwodu) bramek w taki sposób, że jakakolwiek krawędź między dwiema bramami łączy sąsiednie warstwy. $d$ $d$

Biorąc pod uwagę, że ma obwód boolowski o rozmiarze , co możemy powiedzieć o rozmiarze obwodu warstwowego obliczającego ? Istnieje trywialna górna granica: dodając atrapy do na każdej warstwie przecinanej przez krawędź, otrzymujemy warstwowy obwód o wielkości co najwyżej . Ale czy możemy ogólnie poprawić się (np. lub ), lub w przypadku interesującej klasy obwodów? $f$ $s$ $f$ $C$ $O(s^2)$ $O(s\cdot \log s)$ $O(s)$

Tło. To pytanie wynika z ostatnich wyników w kryptografii, które pokazują, jak bezpiecznie obliczyć warstwowe obwody boolowskie o rozmiarze z komunikacją (np. lub ; Próbuję zrozumieć, jak restrykcyjne może być to ograniczenie do warstwowych obwodów boolowskich, zarówno w przypadku obwodów ogólnych, jak i obwodów „naturalnych”. W literaturze nie znalazłem jednak wiele na temat obwodów warstwowych; mile widziane są również odpowiednie wskazówki. $s$ $o(s)$ $s/\log s$ $s/\log\log s)$

circuit-complexity circuits Geoffroy Couteau
źródło

Oto przykład obwodu, który wydaje się trudny do przekształcenia w obwód warstwowy bez znacznego powiększenia. Zdefiniuj aby być jakąś funkcją, którą można obliczyć w rozmiarze . Określić i niech się iteracji . Wtedy ma rozmiar . Trudno jest zbudować układ warstwowy o rozmiarze mniejszym niż . Więc jeśli , być może powinniśmy spodziewać się luki między rozmiarem obwodu a rozmiarem obwodu warstwowego. Nie jest to dowód, tylko sugestywny przykład, który może prowadzić intuicję.

f : {0, 1}^{n - 1} \to {0, 1}

$f:\{0,1\}^{n-1} \to \{0,1\}$

u

$u$

g (x_{1}, \dots, x_{n}) = (x_{2}, \dots, x_{n}, x_{1} \oplus f (x_{2}, \dots, x_{n}))

$g(x_1,\dots,x_n) = (x_2,\dots,x_n,x_1 \oplus f(x_2,\dots,x_n))$

C

$C$

t

$t$

g

$g$

C

$C$

O (t u)

$O(tu)$

Θ (n t)

$\Theta(nt)$

u = o (n)

$u=o(n)$

O ile pamiętam, dla obwodów warstwowych najbardziej znaną dolną granicą jest postać . Jest to szczególnie łatwe do udowodnienia dla funkcji -do- . Weźmy na przykład liniową mapę której ma zera tylko na głównej przekątnej. Następnie musi mieć co najmniej bramek na każdej warstwie, a liczba warstw wynosi co najmniej . Należy pamiętać, że tę funkcję można łatwo obliczyć za pomocą zwykłego obwodu o wielkości . W przypadku funkcji pojedynczego wyjścia możliwe jest również udowodnienie tej samej dolnej granicy, ale nie pamiętam argumentu.

Ω (n \log n)

$\Omega(n \log n)$

n

$n$

n

$n$

A x

$Ax$

A \in {0, 1}^{n \times n}

$A \in \{0,1\}^{n \times n}$

n

$n$

\log_{2} n

$\log_2 n$

O (n)

$O(n)$

Alexander S. Kulikov

Wielkie dzięki za komentarze. @ AlexanderS.Kikikov, czy twój folklor argumentacyjny, czy masz jakiś wskaźnik do pracy na obwodach warstwowych? ma sens - byłbym bardzo niespodzianka czymś mniejszym - ale jest jedyna znana górna granica?

Ω (n \log n)

$\Omega(n \log n)$

O (n^{2})

$O(n^2)$

Geoffroy Couteau

Tak, to chyba folklor. Nie jestem pewien, czy otrzymuję pytanie o górną granicę . Możesz rzucić okiem na następujący artykuł: cs.utexas.edu/~panni/sizedepth.pdf

O (n^{2})

$O(n^2)$

Alexander S. Kulikov

Myślę, że nie znamy ogólnie lepszej transformacji niż . Należy zauważyć, że obwód o rozmiarze i głębokości można przekształcić w obwód warstwowy o rozmiarze co najwyżej . (Który w najgorszym przypadku daje nam obwód o rozmiarze .) Chciałem tylko zaznaczyć, że jeśli moglibyśmy udowodnić niższą granicę o wielkości obwód warstwowy, dałoby nam to superliniową dolną granicę wielkości obwodów o głębokości logarytmicznej dla tej funkcji. To pytanie pozostaje otwarte przez ponad 40 lat.

O (s^{2})

$O(s^2)$

s

$s$

d

$d$

d s

$ds$

O (s^{2})

$O(s^2)$

ω (n \log n)

$\omega(n\log{n})$

Alex Golovnev,

Odpowiedzi:

O ile mi wiadomo, badano trzy klasy obwodów warstwowych. We wszystkich tych definicjach łuki są dozwolone tylko między dwiema sąsiadującymi warstwami.

Obwód nazywa się synchroniczny ( Harper 1977 ), jeśli wszystkie bramki są ułożone w warstwy, a wejścia muszą znajdować się w warstwie 0. (Równoważna definicja: dla dowolnej bramki wszystkie ścieżki od wejść do mają tę samą długość). $g$ $g$
Obwód jest lokalnie synchroniczny ( Belaga 1984 ), jeśli każde wejście występuje dokładnie raz, ale na dowolnej warstwie.
Obwód jest warstwowy ( Gál, Jang 2010 ), jeśli bramki i wejścia są ułożone w warstwy, dane wejściowe mogą występować wiele razy na różnych warstwach. (Definicja równoważna: dla każdej bramki bramki wyjściowej wszystkie ścieżki skierowane od do mają tę samą długość.) $g$ $o$ $g$ $o$

Łatwo zauważyć, że trzy klasy są wymienione od najsłabszych do najsilniejszych (a klasa obwodów nieograniczonych jest jeszcze silniejsza).

Jeśli chodzi o rozmiar obwodu warstwowego obliczającego nieograniczony obwód o rozmiarze , wiemy, co następuje: $s$

Dowolny obwód o rozmiarze może być obliczony przez synchroniczny / lokalnie synchroniczny / warstwowy obwód o rozmiarze ( Wegener 1987, Rozdział 12.1 ). $s$ $s^2$
Trudno znaleźć wyraźną funkcję, która wymaga synchronicznego / lokalnie synchronicznego / warstwowego obwodu o rozmiarze . Rzeczywiście, każdy obwód o rozmiarze i głębokości może być obliczony przez obwód synchroniczny o rozmiarze ( Wegener 1987, sekcja 12.1 ). Zatem nawet jeśli mamy wyraźną funkcję która wymaga obwodów synchronicznych o rozmiarze (niezależnie od jej złożoności w klasie obwodów nieograniczonych), to nie może być obliczone przez obwód o głębokości i rozmiar , który odpowiada od dawna otwartemu pytaniu o złożoności obwodu ( $\omega(s\log{s})$ $s$ $d$ $O(sd)$ $f$ $\omega(n\log{n})$ $f$ $O(\log{n})$ $O(n)$ Valiant 1977 ).
Istnieją wyraźne funkcje

3.1 z dolną granicą dla obwodów synchronicznych, ale górną granicą dla obwodów lokalnie synchronicznych ( Turán 1989 ). $\Omega(n\log{n})$ $O(n)$

3.2 z dolną granicą dla obwodów lokalnie synchronicznych, ale górną granicą dla obwodów warstwowych ( Turán 1989 ). $\Omega(n\log{n})$ $O(n)$

Należy zauważyć, że te dwa wyniki separacji firmy Turán zostały udowodnione dla funkcji z jednym wyjściem. Często o wiele łatwiej jest znaleźć funkcję z wyjściami, która oddziela dwie takie klasy. $n$

Jako przykład rozważmy funkcję której ty bit wyjściowy jest XOR wszystkich wejść z wyjątkiem tego. Tę funkcję można łatwo obliczyć za pomocą obwodu warstwowego o rozmiarze : Najpierw oblicz XOR wszystkich danych wejściowych w warstwach o całkowitej wielkości , a następnie oblicz wszystkie dane wyjściowe w jednej warstwie o wielkości . Z drugiej strony wymaga obwodów synchronicznych o rozmiarze . Rzeczywiście, aby obliczyć parzystość o długości , głębokość obwodu musi wynosić co najmniej . Z drugiej strony każda warstwa musi transmitować $f\colon\{0,1\}^n\to\{0,1\}^n$ $i$ $i$ $O(n)$ $\log{n}$ $n$ $n$ $f$ $\Omega(n\log{n})$ $n-1$ $\Omega(\log{n})$ $n$ bitów informacji, więc jego rozmiar musi wynosić co najmniej $n$ .

Alex Golovnev
źródło