Batas bawah ukuran formula untuk fungsi AC0

Pertanyaan:

Berapa ukuran rumus batas bawah paling dikenal untuk fungsi eksplisit di AC ⁰ ? Apakah ada fungsi eksplisit dengan batas bawah ?$\Omega(n^2)$

Latar Belakang:

Seperti kebanyakan batas bawah, ukuran rumus batas bawah sulit didapat. Saya tertarik pada rumus ukuran batas bawah atas gerbang universal standar yang ditetapkan {DAN, ATAU, TIDAK}.

Ukuran rumus batas bawah yang paling dikenal untuk fungsi eksplisit di atas set gerbang ini adalah untuk fungsi yang didefinisikan oleh Andreev. Batas ini ditunjukkan oleh Håstad, meningkatkan batas bawah Andreev untuk . Batas bawah eksplisit lainnya adalah batas bawah Khrapchenko untuk fungsi paritas.Ω ( n 2.5 - o ( 1 ) ) Ω ( n 2$\Omega(n^{3-o(1)})$$\Omega(n^{2.5-o(1)})$$\Omega(n^2)$

Namun, kedua fungsi ini tidak ada dalam AC ⁰ . Saya bertanya-tanya apakah kita tahu fungsi eksplisit dalam AC ⁰ dengan batas bawah kuadratik (atau lebih baik). Batas terbaik yang saya ketahui adalah batas bawah untuk fungsi Perbedaan Elemen, seperti yang ditunjukkan oleh Nechiporuk. Perhatikan bahwa fungsi perbedaan elemen dalam AC ⁰ , jadi saya mencari batas bawah untuk fungsi AC ⁰ eksplisit yang lebih baik daripada , lebih disukai .Ω ( n 2 / log n ) Ω ( n 2$\Omega(n^2/\log n)$$\Omega(n^2/\log n)$$\Omega(n^2)$

Bacaan lebih lanjut:

Sumber yang bagus tentang topik ini adalah "Kompleksitas Fungsi Boolean: Kemajuan dan Batas" oleh Stasys Jukna. Draf buku tersedia secara gratis di situs webnya.

Pertanyaan yang bagus! Khrapchenko pasti tidak bisa memberikan kuadrat batas bawah untuk fungsi. Batas bawahnya sebenarnya setidaknya kuadrat sensitivitas rata-rata. Dan semua fungsi dalam A C 0 memiliki sensitivitas rata-rata poli-logaritmik. Subbotovskaya-Andreev ternyata bisa juga tidak memberikan fungsi seperti itu karena alasan yang mereka gunakan (hasil pembatasan acak dalam formula jauh lebih kecil) adalah persis alasan memaksa besar A C 0 ukuran sirkuit; Switching Lemma Hastad (saya tidak begitu yakin, hanya intuisi). Satu-satunya harapan adalah Nechiporuk. Tetapi argumennya tidak dapat memberikan lebih dari n 2 / log $AC^0$$AC^0$$AC^0$$n^2/\log n$, dengan alasan teori informasi. Jadi, mungkinkah segala sesuatu dalam memiliki formula ukuran kuadrat (atau bahkan lebih kecil)? Saya tidak percaya, tapi tidak bisa dengan cepat menemukan contoh tandingan. $AC^0$

Sebenarnya, fenomena Allender-Koucky muncul juga dalam konteks lain - dalam kompleksitas grafik. Katakanlah bahwa rangkaian dari variabel merupakan sebuah bipartit n × n graf G pada simpul V = { 1 , ... , 2 n } jika untuk setiap masukan vektor a dengan tepat dua 1s adalah, katakanlah, posisi saya dan j ( i ≤ n , j > n ) sirkuit menerima sebuah simpul IFF i dan $2n$$n\times n$$G$$V=\{1,\ldots,2n\}$$a$$i$$j$$i\leq n$$j>n$$a$$i$$j$berdekatan di . Masalah: menunjukkan grafik eksplisit G yang membutuhkan setidaknya n ϵ gerbang diwakili oleh monoton Σ 3 -circuit. Sepertinya pertanyaan yang tidak bersalah (karena kebanyakan grafik membutuhkan sekitar n 1 / 2 gerbang. Tetapi setiap grafik tersebut akan memberi kita fungsi boolean dari 2 m = 2 log n variabel yang membutuhkan non-monoton sirkuit log mendalam ukuran superlinear (oleh hasil Dengan demikian, bahkan membuktikan n ϵ batas bawah untuk sirkuit kedalaman-3 mungkin menjadi tantangan. $G$$G$$n^{\epsilon}$ $\Sigma_3$$n^{1/2}$$2m=2\log n$$n^{\epsilon}$

Terima kasih, Kaveh, karena ingin melihat bab tentang kompleksitas bukti!

Mengenai pertanyaan Robin, pertama bahwa catatan mengandung fungsi yang membutuhkan rumus (dan bahkan sirkuit) ukuran n k untuk setiap konstanta k . Ini mengikuti, katakanlah, dari fakta sederhana bahwa A C 0 berisi semua DNF dengan monomial yang terus-menerus panjang. Dengan demikian, A C 0 berisi setidaknya exp ( n k ) fungsi yang berbeda, untuk setiap k . Di sisi lain, kita memiliki paling banyak tentang fungsi exp ( t log n ) yang dihitung dengan rumus ukuran $AC^0$ $n^k$$k$$AC^0$$AC^0$$\exp(n^k)$$k$$\exp(t\log n)$$t$.

Aku segera membahas masalah mendapatkan eksplisit batas bawah dari atau lebih besar dengan Igor Sergeev (dari universitas Moskow). Satu kemungkinan bisa menggunakan metode Andreev, tetapi diterapkan pada beberapa fungsi lain yang lebih mudah dihitung daripada Parity. Yaitu, pertimbangkan fungsi n variabel dari bentuk F ( X ) = f ( g ( X 1 ) , … , g ( X b ) ) di mana b = log n dan g adalah fungsi dalam $n^2$$n$$F(X)=f(g(X_1),\ldots,g(X_b))$$b=\log n$$g$ darivariabel n / b ; f adalah beberapa fungsi paling kompleks darivariabel b (hanya keberadaan f sudah cukup). Kita hanya perlu bahwa fungsi g tidak dapat "dibunuh" dalam pengertian berikut: jika kita memperbaiki semua kecualivariabel k dalam X , maka harus dimungkinkan untuk memperbaiki semua kecuali satu variabel tersisa dari g sehingga diperoleh subfungsi dari g adalah variabel tunggal. Kemudian menerapkan argumen Andreev dan menggunakan hasil Hastad yang menyusut konstan setidaknya 2 (tidak hanya 3 /$AC^0$$n/b$$f$$b$$f$$g$$k$$X$$g$$g$$2$$3/2$seperti yang ditunjukkan sebelumnya oleh Sybbotovskaya), batas bawah yang dihasilkan untuk adalah sekitar n 3 / k 2 . Tentu saja, kita tahu bahwa setiap fungsi di A C 0 dapat dibunuh dengan memperbaiki semua tapi n 1 / d variabel, untuk beberapa konstan d ≥ 2 . Tetapi untuk mendapatkan n 2 batas bawah itu akan cukup untuk menemukan fungsi eksplisit di A C 0 yang tidak dapat dibunuh dengan memperbaiki semua tapi, katakanlah, n 1 /$F(X)$$n^3/k^2$$AC^0$ $n^{1/d}$$d\geq 2$$n^2$$AC^0$$n^{1/2}$variabel. Seseorang harus mencari fungsi semacam itu secara mendalam lebih besar dari dua.

Sebenarnya, untuk fungsi seperti di atas, seseorang dapat memperoleh batas bawah tentang n 2 / log n melalui argumen serakah yang sederhana, tanpa Nechiporuk, tanpa Subbotovskaya, dan tanpa batasan acak! Untuk ini, itu hanya cukup bahwa "fungsi dalam" g (Y) adalah non-sepele (tergantung pada semua variabel n / b ). Selain itu, terikat berlaku untuk setiap dasar gerbang fanin konstan, bukan hanya untuk formula De Morgan.$F(X)$$n^2/\log n$$n/b$

Bukti: Mengingat rumus untuk dengan s daun, pilih di setiap blok X i variabel yang muncul terkecil jumlah kali sebagai daun. Kemudian atur semua variabel yang tersisa ke konstanta yang sesuai sehingga setiap g ( X i ) berubah menjadi variabel atau negasinya. Rumus yang diperoleh kemudian akan setidaknya n / b kali lebih kecil dari rumus aslinya. Jadi, s setidaknya n / b = n / log $F(X)$$s$$X_i$$g(X_i)$$n/b$$s$$n/b=n/\log n$kali ukuran rumus dari f , yaitu, s ≥ n 2 - o ( 1 ) . QED$2^b/\log b=n/\log\log n$$f$$s\geq n^{2-o(1)}$

Untuk mendapatkan atau lebih, kita harus memasukkan efek menyusut Subbotovskaya-Hastad di bawah pembatasan acak. Calon yang mungkin adalah beberapa versi fungsi Sipser yang digunakan oleh Hastad untuk menunjukkan bahwa sirkuit kedalaman ( d + 1 ) lebih kuat daripada sirkuit dengan kedalaman d .$n^2$$(d+1)$$d$