Ogólny przegląd metody aproksymacji Razborowa

Jaka jest metoda przybliżenia Razborowa? Czy ktoś może dać ogólny przegląd i intuicję?

Niech będzie funkcją logiczną na bitach. Niech . Niech będzie obwodem na n bitach i rozmiarze bramkach . oznacza także funkcję na bitach obliczonych przez z jako ostatnią bramką. Pierwsze bramek jest dla wejścia . Celem jest wykazanie, że o rozmiarze nie może obliczyć . Rozważ wszystkie obliczenia na wejściach z$f$$n$$Z = f^{-1}(0) \subseteq 2^n$$C$$m$$g_1, \ldots, g_m$$g_i$$n$$g_i$$n$$x_1, \ldots, x_n$$C$$m$$f$$C$$Z$. Obliczenia przypisują wartości wyjściom bramek. Pozwolić$B$ być logiczną algebrą $P(Z)$.

Chodzi o rozważenie dowolnej funkcji $g$ na $n$-bits, jak dobrze to przybliża $f$ na $Z$. Pozwolić$||g|| = \{w \in Z \mid g(w) \neq 0 \}$.

Do ultrafiltru $F \subseteq B$ możemy zdefiniować nowe obliczenia za pomocą ultraproduktu z niego: $c(g_i) = 0$ iff $||g_i|| \not\in F$. Ponieważ ultrafiltr jest zasadniczo zbiorem spójnych obliczeń dla 0 wartości wynikowych$c$jest poprawnym obliczeniem. Wynika z tego$f(c_1, \ldots, c_n) = 0$. Stworzyliśmy nowe obliczenia z istniejących. Ponieważ wszystkie ultrafiltratory w zestawach skończonych są najważniejsze$c_1,\ldots,c_n \in Z$. Działa to w przypadku dowolnego obwodu, nie wykorzystaliśmy faktu, że obwód jest wielkości$m$.

Kolejnym pomysłem jest teraz wykorzystanie skończoności obwodu do skonstruowania nowego wejścia, które jest na zewnątrz $Z$ i $f(w) \neq 0$ ale obwód nie zauważa z powodu swojego ograniczonego rozmiaru i dlatego nadal wyprowadza 0. Więc nie oblicza $f$.

Musimy rozluźnić definicję ultrafiltru, abyśmy mogli uzyskać dane wejściowe na zewnątrz $Z$. Zamiast ultrafiltrów używamy zamkniętych w górę podzbiorów$B$ ($a \in F$ i $a \subseteq b$ implikuje $b \in F$), które zachowują spełniają ($a,b \in F$ implikuje $a \cap b \in F$).

Pozwolić $W_F = \{w \in 2^n \mid w_i = 0 \to ||\lnot x_i|| \in F, w_i \neq 0 \to ||x_i|| \in F\}$. $W_F$ to zestaw danych wejściowych zgodny z $F$. Gdyby$F$ jest liczbą pierwszą ($a \cup b \in F$ implikuje $a \in F$ lub $b \in F$) i niespełnione ($\emptyset \not\in F$), a następnie dla każdego $i$, $F$ zawiera albo $||x_i||$ lub $||\lnot x_i||$ i $W_F$ zawiera tylko jedno wejście.

Będziemy relaksować zachowanie spotkań. Zamiast wszystkich spotkań w algebrze boolowskiej zachowamy niewielką ich liczbę. Pozwolić$|f|$ być najmniejszą liczbą $k$ z spełnia $M = (a_1 \cap b_1, \ldots, a_k \cap b_k)$ tak, że dla wszystkich zamkniętych w górę, niespełnionych, $M$-konserwowanie $F$, $W_F \subseteq Z$.

Pozwolić $m$ być złożonością obwodu $f$. Razborov to udowodnił$\frac{1}{2}|f| \leq m \leq O(|f|^3 + n^3)$.

Zauważ, że ta nierówność dotyczy wszystkich funkcji. Aby udowodnić dolną granicę rozmiaru obwodu$m$ pokaż to wszystkim $m$-spotyka się $M$, tam jest $F$ który spełnia warunki, ale jego $W_F$ nie jest zawarte w $Z$. Co więcej, każdą dolną granicę silnego obwodu można udowodnić tą metodą ze względu na drugą nierówność.

Rzeczywista część dowodu w dolnej granicy obwodu ma to pokazać $m$, dla każdego $m$-Spotyka się z takim $F$. W przypadku obwodów monotonicznych stan około$W_F$ upraszcza $w_i \neq 0 \to ||x_i|| \in F$ więc wymyślanie $F$ jest łatwiej.

Alexander Razborov, O metodzie aproksymacji, 1989. pdf

Mauricio Karchmer, On Proving Lower Bounds for Circuit Size, 1995.

Tim Gowers, metoda przybliżenia Razborowa, 2009. pdf

Oświadczenie : To jest tylko ogólny przegląd mający na celu dać intuicję metodom zastosowanym w najnowszym artykule Bluma.

Spróbuję użyć notacji, która jest bliższa temu, co jest użyte we wspomnianym artykule.

Pozwolić $f$ być funkcją logiczną na $n$ zmienne $x_1,\dots,x_n$. Załóżmy, że chcemy udowodnić, że dowolne logiczne przetwarzanie sieciowe$f$ ma duży rozmiar.

Biorąc pod uwagę pewną sieć logiczną $\beta$ przetwarzanie danych $f$ w węźle wyjściowym rozważ następujący proces.

1. Zamów bramy $\beta$ zgodnie z pewnym porządkiem topologicznym $g_1,g_2,\dots,g_m$ gdzie ostatni węzeł jest węzłem wyjściowym.
2. Dla każdego kroku czasowego $t=1,\dots,m$będziemy zbliżenie funkcję obliczoną przy bramie$g_t$ przez „prostą” funkcję $f_{g_t}$. To przybliżenie może zmienić funkcje obliczane w węzłach poniżej$g_t$ (w szczególności funkcja w węźle wyjściowym $g_m$ mogło się zmienić).

Pod koniec tego procesu aproksymujemy funkcję obliczoną na $g_m$ przez prostą funkcję $f_{g_m}$.

Następnie skonstruuj grupę danych wejściowych testu $T\subseteq \{0,1\}^n$.

Załóżmy, że możemy udowodnić następujące stwierdzenia:

• Przybliżenie każdego pojedynczego węzła jest dobre (tzn. Co najwyżej $e$-Wprowadzono wiele błędów w danych wejściowych z $T$ na każdym etapie zbliżania).
• Żadna prosta funkcja nie jest przybliżona $f$ dobrze (tj. dla dowolnej prostej funkcji $f_{g_m}$, mamy $f_{g_m}\neq f$ na więcej niż $d$ułamek $T$).

Następnie po prostu zliczając liczbę błędów, otrzymujemy to $\beta$ musi mieć przynajmniej $\tfrac{d\lvert T\rvert}{e}$wiele bram.

Jeśli można wykazać, że ten schemat aproksymacji działa dla dowolnej sieci $\beta$ obliczanie funkcji $f$, następnie dochodzimy do dolnej granicy złożoności obwodu $f$.