Dolne granice wielkości formuły dla funkcji AC0

Pytanie:

Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC ⁰ ? Czy istnieje wyraźna funkcja z dolną granicą ?$\Omega(n^2)$

Tło:

Podobnie jak większość dolnych granic, dolne granice formuł są trudne do osiągnięcia. Interesują mnie dolne granice formuły powyżej standardowego uniwersalnego zestawu bram {AND, OR, NOT}.

Najbardziej znaną dolną granicą rozmiaru formuły dla funkcji jawnej w tym zestawie bramek jest dla funkcji zdefiniowanej przez Andreeva. Tę granicę wykazał Håstad, poprawiając dolną granicę Andreeva o Ω ( n 2,5 - $\Omega(n^{3-o(1)})$. Inną wyraźnie niższa granica to Khrapchenko wΩ( N 2 ),dolna granica dla funkcji parzystości.$\Omega(n^{2.5-o(1)})$$\Omega(n^2)$

Jednak te dwie funkcje nie są w AC ⁰ . Zastanawiam się, czy znamy wyraźną funkcję w AC ⁰ z kwadratową (lub lepszą) dolną granicą. Najlepszą znaną mi granicą jest dolna granica dla funkcji odrębności elementu, jak pokazuje Nechiporuk. Zauważ, że funkcja odróżniania elementów jest w AC ⁰ , więc szukam dolnej granicy dla jawnej funkcji AC ^0, która jest lepsza niż Ω ( n 2 / log n ) , najlepiej Ω ( n 2 ) .$\Omega(n^2/\log n)$$\Omega(n^2/\log n)$$\Omega(n^2)$

Dalsza lektura:

Doskonałym źródłem informacji na ten temat jest „Złożoność funkcji logicznej: postępy i granice” autorstwa Stasysa Jukny. Szkic książki jest dostępny bezpłatnie na jego stronie internetowej.

Ładne pytanie! Chrapczenko zdecydowanie nie może dać kwadratowych dolnych granic dla funkcji . Jego dolna granica ma w rzeczywistości co najmniej kwadrat średniej wrażliwości. Wszystkie funkcje w A C 0 mają średnią czułość na logarytmię. Subbotovskaya-Andreev najwyraźniej również nie może dać taką funkcję, ponieważ argument używają (wyniki losowo ograniczenie w znacznie mniejszych wzorów) jest właśnie powód, zmuszając dużą C 0 rozmiar obwodu; Hastad's Switching Lemma (nie jestem do końca pewien, tylko intuicja). Jedyną nadzieją jest Nechiporuk. Ale jego argument nie może dać więcej niż n 2 / log $AC^0$$AC^0$$AC^0$$n^2/\log n$, z przyczyn teoretycznych informacji. Tak więc, może się okazać, że wszystko w ma formuły kwadratowej (lub nawet mniejszym rozmiarze)? Nie wierzę w to, ale nie mogłem szybko znaleźć kontrprzykładu. $AC^0$

W rzeczywistości zjawisko Allendera-Koucky'ego pojawia się również w innym kontekście - w złożoności grafów. Powiedzmy, że obwód zmiennych reprezentuje dwustronny wykres n × n G na wierzchołkach V = { 1 , … , 2 n }, jeżeli dla każdego wektora wejściowego a z dokładnie dwoma 1s jest, powiedzmy, pozycjami i i j ( i ≤ n , j > n ) przyjmuje układ do wierzchołków iff i i $2n$$n\times n$$G$$V=\{1,\ldots,2n\}$$a$$i$$j$$i\leq n$$j>n$$a$$i$$j$sąsiadują z . Problem: pokaż wyraźny wykres G wymagający co najmniej n ϵ bramek reprezentowanych przez monotoniczny Σ 3- obwód. Wydaje się, że w nieszkodliwego mowa (ponieważ większość wykresy wymagają o n 1 / 2 bramy. Jednak każdy taki wykres dałoby logiczną funkcji 2, m = 2 log n zmiennymi wymagające niż monotonowego obwodów dziennika i głębokości superlinear wielkości (wynikami Valiant), więc nawet sprawdzenie n ϵ dolnych granic obwodów na głębokości 3 może być wyzwaniem. $G$$G$$n^{\epsilon}$ $\Sigma_3$$n^{1/2}$$2m=2\log n$$n^{\epsilon}$

Dzięki, Kaveh, za chęć przyjrzenia się rozdziałom dotyczącym złożoności dowodu!

Jeśli chodzi o pytanie Robin, po pierwsze, że uwaga C 0 zawiera funkcje wymagające formuł (a nawet obwodów) w rozmiarze n k dla dowolnej stałej k . Wynika to, powiedzmy, z prostego faktu, że A C 0 zawiera wszystkie DNF o ciągle długich jednomianach. Tak więc, C 0 zawiera co najmniej exp ( n k ) różne funkcje, dla każdego k . Z drugiej strony mamy co najwyżej funkcje exp ( t log n ) obliczalne na podstawie wzorów wielkości t$AC^0$ $n^k$$k$$AC^0$$AC^0$$\exp(n^k)$$k$$\exp(t\log n)$$t$.

Krótko omówiłem kwestię uzyskania wyraźnych dolnych granic lub większych z Igorem Siergiejem (z uniwersytetu w Moskwie). Jedną z możliwości może być zastosowanie metody Andreeva, ale zastosowanej do innej, łatwiejszej do obliczenia funkcji zamiast parzystości. To znaczy, za funkcję n zmiennych postać F ( x ) = f ( g ( x 1 ) , ... , g ( X b ) ) , gdzie b = log n a $n^2$$n$$F(X)=f(g(X_1),\ldots,g(X_b))$$b=\log n$$g$ jest funkcją w z n / b zmiennych; f jest najbardziej złożoną funkcjązmiennych b (wystarczysamo istnienie f ). Potrzebujemy tylko, aby funkcji g nie można było „zabić” w tym sensie: jeśli naprawimy wszystkiezmienneoprócz k w X , to musi być możliwe naprawienie wszystkich oprócz jednej z pozostałych zmiennych g, aby uzyskana podfunkcja g jest pojedynczą zmienną. Następnie stosując argumentację Andreev i za pomocą rezultat Hastad że ciągłe kurczenie się jest co najmniej 2 (nie tylko 3 /$AC^0$$n/b$$f$$b$$f$$g$$k$$X$$g$$g$$2$$3/2$jak wcześniej wykazał Sybbotovskaya), wynikowa dolna granica dla wyniesie około n 3 / k 2 . Oczywiście wiemy, że każda funkcja w A C 0 może zostać zabity przez ustalenie wszystkich, ale n 1 / d zmiennych, dla pewnej stałej d ≥ 2 . Jednak, aby uzyskać n 2 dolna granica to byłoby na tyle, aby znaleźć wyraźną funkcję w A C 0 , która nie może zostać zabity przez ustalenie wszystkich, ale, powiedzmy, n 1 /$F(X)$$n^3/k^2$$AC^0$ $n^{1/d}$$d\geq 2$$n^2$$AC^0$$n^{1/2}$zmienne. Należy szukać takiej funkcji na głębokości większej niż dwie.

W rzeczywistości dla funkcji jak wyżej, można uzyskać dolne granice o n 2 / log n za pomocą prostego argumentu chciwego, bez Nechiporuka, bez Subbotovskaya i bez przypadkowych ograniczeń! W tym celu wystarczy, że „funkcja wewnętrzna” g (Y) jest nietrywialna (zależy od wszystkich jej zmiennych n / b ). Co więcej, granica obowiązuje dla każdej podstawy stałych bram fanowskich, nie tylko dla formuł De Morgana.$F(X)$$n^2/\log n$$n/b$

Dowód: Biorąc pod uwagę wzór na ze s liśćmi, wybierz w każdym bloku X i zmienną, która pojawia się najmniejszą liczbę razy jako liść. Następnie ustaw wszystkie pozostałe zmienne na odpowiednie stałe, tak aby każda g ( X i ) zamieniała się w zmienną lub jej negację. Otrzymany wzór będzie wówczas co najmniej n / b razy mniejszy niż pierwotny wzór. Zatem s wynosi co najmniej n / b = n / log $F(X)$$s$$X_i$$g(X_i)$$n/b$$s$$n/b=n/\log n$ razy większe od rozmiaru formuły z F , to znaczy s ≥ n 2 - O ( 1 ) . CO BYŁO DO OKAZANIA$2^b/\log b=n/\log\log n$$f$$s\geq n^{2-o(1)}$

Aby uzyskać lub więcej, należy zastosować efekt kurczenia Subbotovskaya-Hastad pod losowymi ograniczeniami. Możliwym kandydatem może być jakaś wersja funkcji Sipsera używana przez Hastada do wykazania, że obwody głębokości ( d + 1 ) są silniejsze niż obwody głębokości d .$n^2$$(d+1)$$d$