Beigel-Tarui transformacja układów ACC

Czytam dodatek na temat dolnych granic ACC dla NEXP w książce Arora i Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accupt.pdf Jednym z kluczowych lematów jest transformacja z obwodów w wielomianowe wielomianowe nad liczbami całkowitymi o stopniu polilogarytmicznym i quasipolynomialnym współczynnikami lub równoważnie , klasa obwodów S Y M + , która jest klasą głębokości dwóch obwodów z quasipolomomicznie wieloma bramkami AND na swoim dolnym poziomie z polilogarytmicznym wachlowaniem i symetryczną bramką na najwyższym poziomie.$ACC^{0}$$SYM^{+}$

W dodatku do podręcznika ta transformacja składa się z trzech etapów, przy założeniu, że zestaw bramek składa się z OR, mod , mod 3 i stałej 1 . Pierwszym krokiem jest zmniejszenie wachlarza bramek OR do porządku polilogarytmicznego.$2$$3$$1$

Używanie Bitny-Vazirani Isolation lematu Autorzy otrzymują podanej OR bramy przez wejść postaci O R ( x 1 , . . . , X 2 k ) ,, jeżeli odbiór h być parami niezależne hash , od [ 2 k ] do { 0 , 1 } , a następnie dla każdego niezerowego x ∈ { 0 , 1 } 2 k , z prawdopodobieństwem co najmniej 1 /$2^{k}$$OR (x_{1},...,x_{2^{k}})$$h$$[2^{k}]$$\{ 0,1 \}$$x \in \{0,1\}^{2^{k}}$ będzie utrzymywał, że Σ i : h ( i ) = 1 x i mod  2 .$1/(10k)$$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2$

Nie jest prawdopodobieństwo co najmniej 1 / 2 ? Wydaje się, że 1 / 10 k jest słaby dolny.$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2$$1/2$$1/10k$

Drugim krokiem jest przejście do bram arytmetycznych i spychanie mnożników w dół. W tym kroku przekształcimy obwody boolowskie z danym ciągiem wejściowym binarnym na obwód arytmetyczny z wejściem całkowitym.

Tutaj zauważyć, że otrzymuje się 1 - x 1 x 2 ⋯ x K i M O D P ( x 1 , . . . , X k ) jest zastąpiony przez ( Σ i = 1 , . . . , K x I ) p $OR(x_{1},...,x_{k})$$1-x_{1}x_{2}\cdots x_{k}$$MOD_{p}(x_{1},...,x_{k})$ za pomocą Małego Twierdzenia Fermata.$(\Sigma_{i=1,...,k} x_{i})^{p-1}$

Dlaczego ta wymiana daje równoważny obwód ?$SYM^{+}$

Czy prawdopodobieństwo wynosi co najmniej 1/2? Wydaje się, że 1 / ( 10 k ) jest słabą dolną granicą.$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$$1/(10k)$

W rzeczywistości odpowiedź brzmi „nie”. (Byłoby to posiada z prawdopodobieństwem co najmniej 1 / 2 - ε , jeśli pracowały z ε -biased rodziny mieszania, a nawet za pomocą ε -biased mieszania funkcje dają sposób na poprawę parametrów konstrukcji. Ale niezależność parami niekoniecznie musi być niezależna ε ).$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$$1/2-\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$

Wygląda na to, że brakuje im tutaj dodatkowego kroku. Aby zastosować Valiant-Vazirani bezpośrednio, musisz również losowo wybrać zakres funkcji skrótu. Zamiast wybierać losowe niezależne od par h : [ 2 k ] → { 0 , 1 } , wydaje się, że należy wybrać losowe ℓ ∈ { 2 , … , k + 1 }, a następnie wybrać losowe h niezależne od par h : [ 2 k ] → { 0 , 1 } $h : [2^k]\rightarrow\{0,1\}$$\ell \in \{2,\ldots,k+1\}$$h : [2^k]\rightarrow \{0,1\}^{\ell}$ . (Tutaj celowo używam oświadczenia Valiant-Vazirani Arory-Baraka, znalezionego na stronie 354.) Niech jest liczbą x i = 1 . Valiant-Vazirani mówi, że jeśli wybrałeś ℓ tak, że 2 ℓ - 2 ≤ s ≤ 2 ℓ - 1 , to prawdopodobieństwo, że Σ i : h ( i ) = 1 x i = $s$$x_i=1$$\ell$$2^{\ell-2} \leq s \leq 2^{\ell-1}$$\Sigma_{i:h (i) =1} x_{i} = 1$ (powyżej liczb całkowitych!) Wynosi co najmniej .$1/8$

Więc wybierając losowe i losowe niezależne parami h : [ 2 k ] → { 0 , 1 } ℓ , wtedy masz prawdopodobieństwo co najmniej 1 / ( 8 k ), że Σ i : h ( i ) = 1 x i mod  2 = 1 . Aby zasymulować losowy wybór ℓ (w końcu ich liczba jest logarytmiczna w 2 k ), więc prawdopodobieństwo sukcesu staje się co najmniej$\ell$$h: [2^k]\rightarrow\{0,1\}^{\ell}$$1/(8k)$$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$$\ell$ w obwodzie, możesz po prostu wziąć nad wszystkie możliwe $OR$$\ell$$2^k$ ponownie. Więc zamiastfunkcji skrótu O ( k log s ) z zakresem { 0 , 1 } , będziesz chciał O ( k ) różnych zestawów funkcji skrótu (każdy zestaw ma inny zakres), z$1/8$$O(k\log s)$$\{0,1\}$$O(k)$funkcjami skrótu O ( log s ) w każdym zestawie.$O(\log s)$

Dlaczego ta wymiana daje równoważny obwód SYM +?

$K$$h : \{0,1\}^n \rightarrow \{0,\ldots,K\}$$K$$g : \{0,\ldots,K\}\rightarrow \{0,1\}$$g(h(x_1,\ldots,x_n))$$f$$g$$h$