Referensi tentang Batas Bawah Sirkuit

Pembukaan

Sistem bukti interaktif dan protokol Arthur-Merlin diperkenalkan oleh Goldwasser, Micali dan Rackoff dan Babai pada tahun 1985. Pada awalnya, diperkirakan bahwa yang pertama lebih kuat dari yang terakhir, tetapi Goldwasser dan Sipser menunjukkan bahwa mereka memiliki kekuatan yang sama ( sehubungan dengan pengenalan bahasa). Oleh karena itu, dalam posting ini, saya akan menggunakan dua konsep secara bergantian.

Biarkan menjadi kelas bahasa yang menerima sistem bukti interaktif dengan putaran . Babai membuktikan bahwa . (Hasil yang relativizable.)k I P [ O ( 1 ) ] ⊆ Π P $IP[k]$$k$$IP[O(1)] \subseteq \Pi_2^P$

Pada awalnya, tidak diketahui apakah jumlah putaran yang tidak terikat dapat meningkatkan kekuatan IP. Secara khusus, itu terbukti memiliki relativizations bertentangan: Fortnow dan Sipser menunjukkan bahwa untuk beberapa oracle , itu menyatakan bahwa . (Oleh karena itu, relatif terhadap , bukan merupakan superclass dari PH .)$A$$coNP^A \not\subset IP[poly]^A$$A$$IP[poly]$$PH$

Di sisi lain, makalah berikut:

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

menunjukkan bahwa, untuk beberapa oracle $B$ , kita memiliki $IP[poly]^B \not\subset PH^B$ . (Oleh karena itu, $IP[poly]^B \neq IP[O(1)]^B$ karena seperti yang disebutkan di atas, yang terakhir adalah subkelas dari $\Pi_2^{P,B}$ .)

Pertanyaan

Makalah oleh Aiello, Goldwaseer, dan Hastad (dikutip di atas) menyatakan:

Teknik yang digunakan adalah perpanjangan teknik untuk membuktikan batas bawah pada sirkuit kedalaman kecil yang digunakan dalam [FSS], [Y] dan [H1].

di mana [FSS], [Y] dan [H1] adalah:

[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.

Saya menemukan kertas sangat tua dan sangat sulit untuk diikuti. Saya membaca Bab 14 dari buku Arora & Barak , namun ternyata itu tidak mencakup semua yang saya butuhkan.

Apa referensi tentang "Batas Bawah Sirkuit" yang Anda sarankan?

(Saya secara khusus membutuhkan referensi seperti survei; yang lebih baru dan tidak memerlukan banyak keahlian lebih disukai).

Apa yang Anda inginkan adalah referensi yang baik untuk memahami batas bawah eksponensial untuk sirkuit menghitung fungsi PARITY.$AC^0$

Sekarang Anda belum menyatakan apakah Anda benar-benar ingin memahami buktinya, atau hanya memahami hal-hal pada tingkat tinggi, cara artikel survei akan menjelaskan banyak hal.

Sebuah artikel survei yang baru-baru ini saya baca dan sukai adalah " Kompleksitas fungsi terbatas " oleh Boppana dan Sipser.

Jika Anda benar-benar ingin duduk dan memahami buktinya, maka Anda dapat membaca bukti berdasarkan Switching lemma (yang muncul di koran yang Anda kutip - [FSS], [Y] dan [H1]), atau Razborov-Smolensky bukti.

Untuk bukti menggunakan Switching Lemma, Håstad's Ph.D. tesis adalah bacaan yang baik, jika agak sulit untuk diikuti jika Anda baru ke daerah tersebut. Eksposisi bukti yang lebih baik ada di "Pengantar kompleksitas sirkuit dan panduan untuk bukti Håstad" oleh Allan Heydon. Satu-satunya masalah dengan itu adalah bahwa saya tidak dapat menemukannya secara online, dan saya memiliki salinannya. Saya sangat merekomendasikannya jika Anda baru mengenal kompleksitas sirkuit.

Untuk pendekatan Razborov-Smolensky, cukup google untuk itu dan Anda akan mendapatkan banyak catatan kuliah. Saya memahami batas bawah dari tiga catatan kuliah ini: Sanjeev Arora , Madhu Sudan dan Kristo ff er Arnsfelt Hansen .

Jika Anda menemukan eksposisi Switching Lemma dalam tesis Hastad sulit diikuti, Anda dapat mencoba Paul Beame's `` A Switching Lemma Primer '' , yang memiliki versi berbeda karena Razborov (yang juga secara eksplisit menggunakan pohon keputusan, sesuatu yang sangat penting dalam beberapa aplikasi dari Switching Lemma)

Buku ini bagus untuk menjelaskan batas bawah, jika Anda memiliki akses ke sana.

Pengantar Kompleksitas Sirkuit oleh Heribert Vollmer.

Saya baru saja selesai membacanya, dan meskipun dikatakan "pengantar" adalah perawatan yang sangat mendalam pada kompleksitas sirkuit. Ini menjelaskan dengan detail semua teknik (paling populer) untuk membuktikan batas bawah sirkuit pada bab 3.

Referensi yang lebih baru adalah Kompleksitas Fungsi Boolean oleh Stasys Jukna. Anda hanya perlu mengiriminya email atau mengisi formulir untuk mendapatkan pdf konsep.

Referensi yang lebih tua tetapi masih bagus adalah survei The Complexity of Finite Functions oleh Boppana dan Sipser. Survei ini sangat mudah dibaca dibandingkan dengan sumber lain.

Referensi bagus lainnya adalah buku Boolean Functions and Computation Models oleh Clote dan Kranakis.

Saya bukan spesialis, tetapi mungkin ada informasi menarik di buku biru ( http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ ).

Ada juga sebuah makalah oleh Allender pada tahun 1997: Kompleksitas Sirkuit sebelum Fajar Milenium Baru

Emanuele Viola telah menerbitkan buku " On the Power of Small-Depth Computation " yang mencakup banyak hasil pada batas bawah sirkuit.

Versi awal buku ini dapat ditemukan di sini .