Dolne granice wielkości formuły dla funkcji AC0

25

Pytanie:

Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC 0 ? Czy istnieje wyraźna funkcja z dolną granicą ?Ω(n2)

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 - oΩ(n3o(1)). Inną wyraźnie niższa granica to Khrapchenko wΩ( N 2 ),dolna granica dla funkcji parzystości.Ω(n2.5o(1))Ω(n2)

Jednak te dwie funkcje nie są w AC 0 . Zastanawiam się, czy znamy wyraźną funkcję w AC 0 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 0 , więc szukam dolnej granicy dla jawnej funkcji AC 0, która jest lepsza niż Ω ( n 2 / log n ) , najlepiej Ω ( n 2 ) .Ω(n2/logn)Ω(n2/logn)Ω(n2)

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 A C 0 ? czyli jeśli mamy n 1 + ε dolne (gdzie ε nie jest zależna od głębokości), a następnie otrzymujemy superpoly dolne. AC0AC0n1+ϵϵ
Kaveh
@Kaveh: Nie jestem pewien, czy rozumiem. Mamy już dolną granicę dla funkcji w A C 0 (odrębność elementu). Ω(n2/logn)AC0
Robin Kothari
Przepraszamy, zamień superlinię na super-kwadratową. Mam na myśli coś podobnego do wyniku Allendera-Koucky'ego dla . Wykładnik dla A C 0 może być większy. Taki wynik może wyjaśnić, dlaczego trudno jest znaleźć C 0 lowerbounds dla A C 0 funkcji. TC0AC0AC0AC0
Kaveh
Wydaje się, że jakikolwiek problem, który jest kompletny dla ramach redukcji Turinga N C 0, 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. AC0NC0
Kaveh

Odpowiedzi:

15

Ł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 nAC0AC0AC0n2/logn, 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. AC0

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 j2nn×nGV={1,,2n}aijinj>naijsą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. GGnϵ Σ3n1/22m=2lognnϵ

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
2
Wielkie dzięki za odpowiedź! Jeśli pomyślisz o funkcji w , którą przypuszczasz, że wymaga wzoru o wielkości Ω ( n 2 ) , będę zainteresowany. AC0Ω(n2)
Robin Kothari,
12

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 tAC0 nkkAC0AC0exp(nk)kexp(tlogn)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 gn2nF(X)=f(g(X1),,g(Xb))b=logng 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 / 2AC0n/bfbfgkXgg23/2jak 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 / 2F(X)n3/k2AC0 n1/dd2n2AC0n1/2zmienne. 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)n2/lognn/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 nF(X)sXig(Xi)n/bsn/b=n/logn razy większe od rozmiaru formuły z F , to znaczy s n 2 - O ( 1 ) . CO BYŁO DO OKAZANIA2b/logb=n/loglognfsn2o(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 .n2(d+1)d

Stasys
źródło