Referencje na temat dolnych granic obwodu

Preambuła

Interaktywne systemy dowodowe i protokoły Arthura-Merlina zostały wprowadzone przez Goldwassera, Micali i Rackoffa i Babai w 1985 roku. Początkowo sądzono, że ten pierwszy jest potężniejszy od drugiego, ale Goldwasser i Sipser wykazali, że mają taką samą moc ( w odniesieniu do rozpoznawania języka). Dlatego w tym poście użyję tych dwóch pojęć zamiennie.

Niech $IP[k]$ będzie klasą języków dopuszczających interaktywny system z rundami. Babai okazało się, że . (Wynik relatywny.)I P [ O ( 1 ) ] ⊆ Õ P $k$$IP[O(1)] \subseteq \Pi_2^P$

Na początku nie było wiadomo, czy nieograniczona liczba rund może zwiększyć moc IP. W szczególności, wykazano, mają przeciwstawne relativizations: Fortnow i Sipser wykazały, że w niektórych oracle , ustala się, że . (Dlatego w odniesieniu do , nie jest nadklasą .)$A$$coNP^A \not\subset IP[poly]^A$$A$$IP[poly]$$PH$

Z drugiej strony następujący papier:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

przedstawia, że dla niektórych oracle , mamy . (Dlatego ponieważ jak wspomniano powyżej, ta ostatnia jest podklasą .)$B$$IP[poly]^B \not\subset PH^B$$IP[poly]^B \neq IP[O(1)]^B$$\Pi_2^{P,B}$

Pytanie

Artykuł Aiello, Goldwaseera i Hastada (cytowany powyżej) stwierdza:

Zastosowane techniki są rozszerzeniem technik dowodzenia dolnych granic na obwodach o małej głębokości stosowanych w [FSS], [Y] i [H1].

gdzie [FSS], [Y] i [H1] to:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

Znalazłem bardzo stare i niezwykle trudne do naśladowania artykuły. Przeczytałem rozdział 14 książki Arora i Baraka , ale najwyraźniej nie obejmuje wszystkiego, czego potrzebuję.

Jakie odniesienia do „Obwodów dolnych granic” sugerujesz?

(Szczególnie potrzebuję referencji podobnych do ankiet; te, które są nowsze i nie wymagają dużej wiedzy, są bardziej preferowane).

To, czego chcesz, to dobre odniesienie do zrozumienia wykładniczych dolnych granic obwodów obliczających funkcję parzystości.$AC^0$

Teraz nie powiedziałeś, czy naprawdę chcesz zrozumieć dowód, czy po prostu rozumieć rzeczy na wysokim poziomie, tak jak artykuł w ankiecie wyjaśniłby to.

Artykuł w ankiecie, który niedawno przeczytałem i polubiłem, to „ Złożoność funkcji skończonych ” Boppany i Sipsera.

Jeśli naprawdę chcesz usiąść i zrozumieć dowód, możesz albo przeczytać dowody oparte na lemacie Przełączania (które pojawiają się w cytowanych artykułach - [FSS], [Y] i [H1]), lub Razborov-Smoleński dowód.

Aby uzyskać dowody przy użyciu Switching Lemma, doktor Håstad. praca jest dobra, jeśli trudno jest ją śledzić, jeśli jesteś nowy w okolicy. Lepsze przedstawienie dowodu znajduje się w „Wprowadzenie do złożoności obwodu i przewodnik po dowodzie Håstad” Allana Heydona. Jedyny problem polega na tym, że nie mogę go znaleźć w Internecie i mam wersję papierową. Naprawdę polecam, jeśli jesteś nowy w złożoności obwodu.

Jeśli chodzi o podejście Razborov-Smolensky, po prostu google, a dostaniesz kilka notatek z wykładów. Zrozumiałem dolną granicę tych trzech notatek z wykładów: Sanjeev Arora , Madhu Sudan i Kristooer Arnsfelt Hansen .

Jeśli uważasz, że ekspozycja Switching Lemma w pracy Hastada jest trudna do naśladowania, możesz wypróbować Paula Beame'a `` A Switching Lemma Primer '' , który ma inną wersję ze względu na Razborov (który również wyraźnie wykorzystuje drzewa decyzyjne, co jest kluczowe w niektórych zastosowaniach Switching Lemma)

Ta książka jest świetna do wyjaśniania dolnych granic, jeśli masz do niej dostęp.

Wprowadzenie do złożoności obwodu autorstwa Heriberta Vollmera.

Właśnie skończyłem ją czytać i chociaż mówi „wprowadzenie” jest bardzo głębokim podejściem do złożoności obwodu. Wyjaśnia szczegółowo wszystkie (najpopularniejsze) techniki dowodzenia dolnych granic obwodu w rozdziale 3.

Nowszym odniesieniem byłaby złożoność funkcji boolowskich autorstwa Stasysa Jukny. Wystarczy wysłać mu wiadomość e-mail lub wypełnić formularz, aby uzyskać wersję roboczą pdf.

Starsze, ale wciąż miłe referencje to badanie Złożoność funkcji skończonych autorstwa Boppany i Sipsera. Ta ankieta jest bardzo czytelna w porównaniu do innych źródeł.

Innym dobrym odniesieniem jest książka Boolean Functions and Computation Models autorstwa Clote i Kranakis.

Nie jestem specjalistą, ale prawdopodobnie niebieska księga zawiera prawdopodobnie interesujące informacje ( http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ ).

Istnieje także artykuł Allendera z 1997 roku: Złożoność obwodu przed świtem nowego tysiąclecia

Emanuele Viola opublikował książkę „ O mocy obliczeń małej głębokości ”, która zawiera wiele wyników dotyczących dolnych granic obwodu.

Wstępną wersję książki można znaleźć tutaj .