Referencje na temat dolnych granic obwodu


21

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 jaP.[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 2kjaP.[O(1)]Π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ą .)ZAdooN.P.ZAjaP.[poly]ZAZAjaP.[poly]P.H.

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ą .)bjaP.[poly]bP.H.bjaP.[poly]bjaP.[O(1)]bΠ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).


2
jeszcze inne odniesienie: notatki z wykładu Avi Wigdersona na temat dolnych granic dla stałej głębokości i obwodów monotonicznych (ten link pochodzi ze strony internetowej projektu Arora-Barak).
Alessandro Cosentino

Odpowiedzi:


14

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

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 .


Czy sugeruje Pan jakikolwiek sposób uzyskania kopii dowodu Allana Heydona?
MS Dousti

@Sadeq: Nie mam pojęcia. Mam to z mojej biblioteki. Jest wymieniony na stronie raportów technicznych CMU ( cs.cmu.edu/~clamen/reports/1990.html ) jako raport techniczny jako CMU-CS-90-141, ale nie ma łącza do pobrania lub znalezienia go w dowolnym miejscu online. Możesz spróbować wysłać wiadomość e-mail do autora.
Robin Kothari,

1
W końcu dostałem link do raportu technicznego Allana Heydona dotyczącego repozytorium CMU .
MS Dousti

14

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)


14

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.


12

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.



Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.