Status pada sirkuit batas bawah untuk sirkuit kedalaman yang dibatasi polylog

Kompleksitas rangkaian bounded depth adalah salah satu bidang penelitian utama dalam teori kompleksitas sirkuit. Topik ini memiliki asal dalam hasil seperti "fungsi paritas tidak dalam " dan "fungsi mod tidak dihitung oleh ", di mana adalah kelas bahasa yang dapat ditentukan oleh non-seragam, kedalaman konstan, ukuran polinomial, kipas-dalam tanpa batas AND, OR, NOT dan gerbang modulo , di mana . Namun, mendapatkan hasil batas bawah yang konkret pada sirkuit kedalaman polylogaritmik tampaknya tidak terjangkau dengan menggunakan metode klasik seperti membatasi input dan mendekati polinomial pada bidang terbatas.$AC^{0}$$p$$AC^{0}[q]$$AC^0[q]$$q$$\gcd(p,q)=1$

Saya tahu makalah STOC'96 yang mengarah pada teori kompleksitas geometris dan yang menunjukkan bahwa komputasi paralel yang efisien menggunakan operasi tanpa bit-wise tidak dapat menghitung masalah aliran biaya minimum.

Ini berarti bahwa dalam pengaturan terbatas tertentu, kami dapat membuktikan batas bawah untuk beberapa masalah P -complete.$NC$$P$

Pertama, apakah ada metode atau teknik lain yang mungkin merupakan pendekatan yang masuk akal untuk membuktikan sirkuit kedalaman polylogarithmic batas bawah?

Kedua, seberapa bermanfaatkah pernyataan berikut untuk komunitas teori?

Ukuran sirkuit $NC$ menghitung fungsi Boolean $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ setidaknya $l$ , di mana $l$ adalah beberapa kuantitas matematika tergantung pada kekerasan dari fungsi target $f$ . Nilai $l$ dapat berupa, misalnya, jumlah kombinatorial seperti perbedaan, kuantitas aljabar linier seperti pangkat jenis matriks tertentu atas suatu bidang, atau jumlah yang sama sekali baru yang sebelumnya tidak pernah digunakan dalam teori kompleksitas.

Pada teknik-teknik untuk membuktikan batas bawah kedalaman poly-log, semua pendekatan saat ini bekerja di bawah pengaturan terbatas . Seperti, dalam pekerjaan yang mengarah ke GCT yang Anda sebutkan, batas bawah berlaku untuk model PRAM terbatas tanpa operasi bit.

Di bawah batasan lain, yang merupakan batasan monoton untuk fungsi monoton boolean, ada pendekatan Fourier-analitik (atau enumeratif-kombinatorial) untuk membuktikan batas bawah sirkuit monoton dalam kedalaman, dalam pekerjaan bersama saya dengan Aaron Potechin ( ECCC dan STOC ). Ini meningkatkan hasil sebelumnya oleh Ran Raz dan Pierre McKenzie, yang memperluas kerangka permainan komunikasi Mauricio Karchmer dan Avi Wigderson tentang kedalaman sirkuit.

Jalur penelitian lain untuk memperluas permainan Karchmer-Wigderson diusulkan sebagai game komunikasi yang dirujuk oleh Scott Aaronson dan Avi Wigderson, yang perpanjangannya ke protokol yang saling bersaing disarankan sebagai pendekatan untuk memisahkan NC dari P oleh Gillat Kol dan Ran Raz ( ECCC dan ITCS ).

Selain mempelajari pembatasan sintaksis monotonisitas, ada pendekatan untuk mempelajari pembatasan semantik terkait dengan permainan kerikil (disebut program percabangan hemat) oleh Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, dan Rahul Santhanam. Ada batas bawah yang kuat di bawah batasan hemat oleh Dustin Wehr, cocok dengan batas atas yang paling dikenal untuk masalah P-complete. Hasil ini menyangkut kompleksitas ruang deterministik, yang menurunkan batas waktu paralel atau kedalaman rangkaian dengan hasil simulasi yang diketahui (misalnya sejak ).$\text{AlternatingTime}[t] \subseteq \text{DeterministicSpace}[t]$

Tentang pertanyaan yang berkaitan dengan ukuran dan kedalaman rangkaian, pendekatan berikut mungkin terkait. Richard Lipton dan Ryan Williams menunjukkan bahwa, mengingat batas bawah yang cukup kuat pada kedalaman (yaitu ), ukuran batas bawah yang lemah (yaitu n 1 + Ω ( 1 ) ) dapat memisahkan NC dari P. Hasil ini mengikuti dari argumen trade-off ukuran-mendalam berdasarkan simulasi penghormatan blok. Sebuah awal hasil pada perdagangan kedalaman untuk ukuran adalah karena Allender dan Koucký berdasarkan pada gagasan diri reducibility, tetapi belajar kelas kompleksitas yang lebih kecil seperti NC 1 dan NL.$n^{1-O(1)}$$n^{1+\Omega(1)}$$^1$

Perhatikan bahwa di antara pendekatan yang disebutkan di atas, beberapa dari mereka mempertimbangkan ukuran dan kedalaman sirkuit, sementara pendekatan lain hanya mempertimbangkan kedalaman sirkuit. Secara khusus, pendekatan semi-algebro-geometri Mulmuley , pendekatan protokol bersaing-prover dipelajari oleh Kol-Raz , dan pendekatan trade-off ukuran-kedalaman Allender – Koucký dan Lipton-Williams semuanya menyangkut ukuran dan kedalaman sirkuit. Hasil dalam Chan-Potechin , Raz-McKenzie , Cook-McKenzie-Wehr-Braverman-Santhanam , dan Wehr memberikan batas kedalaman sirkuit lebih rendah di bawah pengaturan terbatas terlepas dari ukuran. Juga, permainan komunikasi yang dirujuk dariAaronson – Wigderson hanya menyangkut kedalaman sirkuit.

Masih konsisten dengan pengetahuan kami bahwa beberapa masalah P-complete tidak dapat dihitung oleh sirkuit dengan kedalaman kecil (yaitu ), terlepas dari ukurannya. Jika ukuran tidak penting untuk sirkuit dengan kedalaman kecil (dari fan-in yang dibatasi), maka mungkin masuk akal untuk lebih fokus pada kedalaman sirkuit, daripada fokus pada ukuran sirkuit dengan kedalaman kecil.$\log^{O(1)}n$

Mengikuti saran Kaveh, saya menempatkan komentar saya sebagai jawaban (diperluas).

Mengenai $Q1$ , kata hati-hati adalah dalam urutan: bahkan kedalaman logaritmik jika jauh dari dipahami, tidak berbicara tentang poli-logaritma. Jadi, di dunia non-monoton, masalah sebenarnya jauh lebih tidak ambisius:

Beating Log-depth Problem: Buktikan batas bawah super-linear (!) Untuk sirkuit $NC^1$

Masalahnya tetap terbuka (untuk saat ini lebih dari 30 tahun) bahkan untuk linear -circuits. Ini adalah sirkuit fanin- 2 atas dasar { ⊕ , 1 } , dan mereka menghitung transformasi linear f ( x ) = A x lebih dari G F ( 2 ) . Penghitungan mudah menunjukkan bahwa hampir semua matriks A membutuhkan gerbang Ω ( n 2 / log n ) , dalam kedalaman apa pun. $NC^1$$2$$\{\oplus,1\}$$f(x)=Ax$$GF(2)$$A$$\Omega(n^2/\log n)$

Mengenai $Q2$ : Ya, kami memiliki beberapa langkah aljabar / kombinatorik, batas bawah yang akan mengalahkan sirkuit log-depth. Sayangnya, sejauh ini, kami tidak dapat membuktikan batas yang cukup besar pada langkah-langkah ini. Katakanlah, linear -circuits, seperti mengukur adalah kekakuan R A ( r ) dari matriks A . Ini adalah jumlah entri A terkecil yang perlu diubah untuk mengurangi peringkat menjadi r . Mudah untuk menunjukkan bahwa R A ( r ) ≤ ( n $NC^1$ $R_A(r)$$A$$A$$r$ berlaku untuk setiap boolean n × n matriks A , dan Valiant (1977) telah menunjukkan bahwa ikatan ini ketat untuk hampir semua matriks. Untuk mengalahkan sirkuit log-depth, cukup untuk memperlihatkan urutanmatriksboolean n × n A sedemikian rupa sehingga$R_A(r)\leq (n-r)^2$$n\times n$$A$$n\times n$$A$

untuk konstanta ϵ , δ > 0 . $R_A(\epsilon n)\geq n^{1+\delta}$$\epsilon,\delta>0$

Yang terbaik yang kita ketahui sejauh ini adalah matriks dengan R A ( r ) ≥ ( n 2 / r ) log ( n / r ) . Untuk Sylvester matriks (yaitu inner matriks produk), yang batas bawah dari Ω ( n 2 / r ) adalah mudah untuk menunjukkan . $A$$R_A(r)\geq (n^2/r)\log(n/r)$$\Omega(n^2/r)$

Kami memiliki langkah-langkah kombinatorial untuk umum (non-linear) -circuits, serta Untuk bipartit n × n graph G , biarkan t ( G ) menjadi nomor terkecil t sehingga G dapat ditulis sebagai persimpangan t bipartit grafik, masing-masing menjadi sebuah serikat paling t grafik bipartit lengkap. Untuk mengalahkan sirkuit log-depth umum, itu akan cukup untuk menemukan urutan grafik$NC^1$$n\times n$$G$$t(G)$$t$$G$$t$$t$

untuk konstanta ϵ > $t(G_n)\geq n^{\epsilon}$$\epsilon >0$

(lihat, misalnya di sini tentang bagaimana hal ini terjadi). Sekali lagi, hampir semua grafik memiliki . Namun, yang terbaik tetap batas bawah t ( G ) ≥ log 3 n untuk matriks Sylvester, karena Lokam . $t(G)\geq n^{1/2}$$t(G)\geq \log^3 n$

Akhirnya, izinkan saya menyebutkan bahwa kita bahkan memiliki ukuran kombinatorial "sederhana" (kuantitas) yang lebih rendah (linier) yang terikat di bawahnya yang akan menghasilkan bahkan batas bawah eksponensial (!) Untuk sirkuit non-monoton. Untuk bipartit graph G , biarkan c ( G ) menjadi jumlah terkecil fanin- 2 union ( ∪ ) dan persimpangan ( ∩ ) operasi diperlukan untuk menghasilkan G ketika mulai dari bintang; sebuah bintang adalah himpunan sisi-sisi yang menghubungkan satu simpul dengan semua simpul di sisi lainnya. Hampir semua grafik memiliki c ( G ) = Ω ( n $n\times n$$G$$c(G)$$2$$\cup$$\cap$$G$ . Di sisi lain, batas bawah$c(G)=\Omega(n^2/\log n)$

untuk konstanta ϵ > $c(G_n)\geq (4+\epsilon)n$$\epsilon>0$

akan berarti batas bawah di non-monoton kompleksitas rangkaian dari fungsi boolean eksplisit f G dari N variabel. Jika G adalah n × m grafik dengan m = o ( n ) , maka bahkan batas bawah c ( G n ) ≥ ( 2 + ϵ ) n sudah cukup (lagi, lihat, misalnya di sini tentang bagaimana hal ini terjadi). Batas bawah c ( $\Omega(2^{N/2})$$f_G$$N$$G$$n\times m$$m=o(n)$$c(G_n)\geq (2+\epsilon)n$ dapat ditampilkan untuk grafik yang relatif sederhana. Masalahnya, bagaimanapun, adalah melakukan ini dengan " - ϵ " diganti dengan " + ϵ ". Tindakan yang lebih kombinatorial menurunkan-bounding kompleksitas sirkuit (termasuk A C C -circuits) dapat ditemukan dalam buku. $c(G)\geq (2-\epsilon)n$$-\epsilon$$+\epsilon$$ACC$

PS Jadi, apakah kita dengan faktor konstan dari menunjukkan P ≠ N P ? Tentu saja tidak. Saya menyebutkan ukuran terakhir ini c ( G ) hanya untuk menunjukkan bahwa seseorang harus memperlakukan "amplifikasi" (atau "pembesaran") dari batas bawah dengan porsi skeptisisme yang sehat: meskipun batas-batas yang kita butuhkan terlihat "polos", jauh lebih kecil ( linear) daripada hampir semua grafik membutuhkan (kuadratik), kesulitan yang melekat untuk membuktikan batas bawah (lemah) mungkin bahkan lebih besar. Tentu saja, setelah menemukan ukuran kombinatorial, kita dapat mengatakan sesuatu tentang sifat fungsi apa yang membuat mereka sulit dikomputasi. Ini mungkin berguna untuk membuktikan tidak langsung$2+\epsilon$$P\neq NP$$c(G)$batas bawah: beberapa kelas kompleksitas berisi fungsi yang membutuhkan sirkuit atau rumus besar. Tetapi tujuan utamanya adalah menghasilkan fungsi keras eksplisit , yang definisinya tidak memiliki "bau algoritmik", tidak memiliki aspek kompleksitas tersembunyi.