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 $\Omega(n^{3-o(1)})$ . Inną wyraźnie niższa granica to Khrapchenko wdolna 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ż , najlepiej . $\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.

— Robin Kothari
źródło

Czy przyczyną braku superliniowych dolnych granic dla funkcji

być pewnego rodzaju samoodwracalność funkcji

? czyli jeśli mamy

dolne (gdzie

nie jest zależna od głębokości), a następnie otrzymujemy superpoly dolne.

A C^{0}

$AC^0$

A C^{0}

$AC^0$

n^{1 + ϵ}

$n^{1+\epsilon}$

ϵ

$\epsilon$

— Kaveh

@Kaveh: Nie jestem pewien, czy rozumiem. Mamy już dolną granicę

dla funkcji w

(odrębność elementu).

Ω (n^{2} / \log n)

$\Omega(n^2/\log n)$

A C^{0}

$AC^0$

— Robin Kothari

Przepraszamy, zamień superlinię na super-kwadratową. Mam na myśli coś podobnego do wyniku Allendera-Koucky'ego dla

. Wykładnik dla

może być większy. Taki wynik może wyjaśnić, dlaczego trudno jest znaleźć

lowerbounds dla

funkcji.

T C^{0}

$TC^0$

A C^{0}

$AC^0$

A C^{0}

$AC^0$

A C^{0}

$AC^0$

— Kaveh

Wydaje się, że jakikolwiek problem, który jest kompletny dla

ramach redukcji Turinga

jest silnie samoczynnie redukowalny, ale nie wydaje się, że daje to to, czego się spodziewałem, ponieważ wielkość samoczynnej redukcji może być wielomianowo duża.

A C^{0}

$AC^0$

N C^{0}

$NC^0$

— Kaveh

Odpowiedzi:

Ł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 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żą 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ż $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 na wierzchołkach jeżeli dla każdego wektora wejściowego z dokładnie dwoma 1s jest, powiedzmy, pozycjami i ( , ) przyjmuje układ wierzchołków iff 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 wymagający co najmniej bramek reprezentowanych przez monotoniczny obwód. Wydaje się, że w nieszkodliwego mowa (ponieważ większość wykresy wymagają o bramy. Jednak każdy taki wykres dałoby logiczną funkcji zmiennymi wymagające niż monotonowego obwodów dziennika i głębokości superlinear wielkości (wynikami Valiant), więc nawet sprawdzenie 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}$

— Stasys
źródło

Witamy w cstheory. :) (przy okazji, twoja nowa książka wygląda dość interesująco, niestety nie jestem rodzimym językiem angielskim, więc nie mogę pomóc w jej

— korekcie

W rzeczywistości wszelkie komentarze / krytycy dotyczące treści / odniesień itp. Są w tym momencie również bardzo ważne. Obecna wersja jest tutaj . Użytkownik: przyjaciel Hasło: catchthecat

— Stasys

Dziękuję :) Przeczytam ostatnie rozdziały o złożoności dowodu zdania.

— Kaveh

Wielkie dzięki za odpowiedź! Jeśli pomyślisz o funkcji w

, którą przypuszczasz, że wymaga wzoru o wielkości

, będę zainteresowany.

A C^{0}

$AC^0$

Ω (n^{2})

$\Omega(n^2)$

— Robin Kothari,

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 zawiera funkcje wymagające formuł (a nawet obwodów) w rozmiarze dla dowolnej stałej . Wynika to, powiedzmy, z prostego faktu, że zawiera wszystkie DNF o ciągle długich jednomianach. Tak więc, zawiera co najmniej różne funkcje, dla każdego . Z drugiej strony mamy co najwyżej funkcje obliczalne na podstawie wzorów wielkości $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ę zmiennych postać , gdzie a $n^2$ $n$ $F(X)=f(g(X_1),\ldots,g(X_b))$ $b=\log n$ $g$ jest funkcją w z zmiennych; jest najbardziej złożoną funkcjązmiennych (wystarczysamo istnienie ). Potrzebujemy tylko, aby funkcji nie można było „zabić” w tym sensie: jeśli naprawimy wszystkiezmienneoprócz w , to musi być możliwe naprawienie wszystkich oprócz jednej z pozostałych zmiennych aby uzyskana podfunkcja jest pojedynczą zmienną. Następnie stosując argumentację Andreev i za pomocą rezultat Hastad że ciągłe kurczenie się jest co najmniej (nie tylko $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 . Oczywiście wiemy, że każda funkcja w może zostać zabity przez ustalenie wszystkich, ale zmiennych, dla pewnej stałej . Jednak, aby uzyskać dolna granica to byłoby na tyle, aby znaleźć wyraźną funkcję w , która nie może zostać zabity przez ustalenie wszystkich, ale, powiedzmy, $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 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 ). 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 liśćmi, wybierz w każdym bloku 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 zamieniała się w zmienną lub jej negację. Otrzymany wzór będzie wówczas co najmniej razy mniejszy niż pierwotny wzór. Zatem wynosi co najmniej $F(X)$ $s$ $X_i$ $g(X_i)$ $n/b$ $s$ $n/b=n/\log n$ razy większe od rozmiaru formuły z , to znaczy . 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 są silniejsze niż obwody głębokości . $n^2$ $(d+1)$ $d$

— Stasys
źródło