Kompleksitas sirkuit yang dihitung dari masalah keputusan

9

Adakah yang telah mengeksplorasi apa kompleksitas sirkuit dari masalah keputusan klasik seperti Primes atau Graph-Isomorphism untuk ukuran input ? $N$

Sementara kebanyakan orang tertarik pada bagaimana penskalaan berjalan sebagai , saya pikir itu juga akan menarik untuk melihat bagaimana ini tumbuh untuk N. kecil. Tentu, kita sekarang tahu Primes ada di P, tetapi akan rapi untuk lihat bagaimana ia tumbuh, dan mungkin bahkan perubahan tajam dalam tingkat pertumbuhan grafik karena inputnya cukup besar sehingga algoritma yang berbeda menjadi lebih efisien. $N \to \infty$

Bahkan ada kemungkinan (tidak mungkin) bahwa seseorang dapat mengekstraksi dari rangkaian sirkuit suatu algoritma umum.

Sepertinya pendekatan ini dapat menjawab pertanyaan yang berbeda dari biasanya tentang . Dengan kemajuan pengetahuan algoritma (pemecah SAT, dll.) Dan kekuatan komputasi super, jawaban konkret dapat diperoleh untuk kecil . $N \to \infty$ $N$

Apakah ada referensi atau daftar hasil untuk orang yang secara eksplisit menghitung kompleksitas rangkaian masalah keputusan untuk kecil ? $N$

Jika ada orang yang mengerjakan ini, algoritma apa yang mereka gunakan saat ini untuk menyelesaikan masalah rangkaian minimal (diberi fungsi boolean dan serangkaian gerbang, mengeluarkan rangkaian menggunakan gerbang minimal yang diperlukan)?

cc.complexity-theory reference-request circuit-complexity TigerSpots
sumber

tampaknya hampir mustahil untuk menyerang dari arah ini karena bahkan tidak dapat menghitung sirkuit optimal untuk masalah yang sangat "kecil". ini tampaknya pada dasarnya merupakan hasil dari kompleksitas kolmogorov. satu arah lain yang tampaknya menjanjikan / setara, tidak terlalu dikenal atau banyak dipelajari, adalah melalui kompleksitas grafik yang tampaknya memungkinkan studi masalah "lebih kecil" tetapi masih dengan implikasi besar misalnya pada pemisahan kelas kompleksitas ... alias disebut "pembesaran lemma" dll

vzn

7

Ya, ini adalah ide alami dan orang-orang telah memikirkannya. Singkatnya, masalahnya adalah bahwa pemecah SAT / QBF yang mutakhir sekalipun memungkinkan untuk menemukan sirkuit yang sangat kecil saja (dengan sekitar 10-12 gerbang), tidak untuk mengatakan tentang membuktikan bahwa tidak ada sirkuit kecil. Beberapa referensi:

Ryan Williams, Menerapkan praktik ke teori (2008):

Pengetahuan kami tentang kompleksitas sirkuit Boolean cukup buruk. <...> Salah satu alasan bagus mengapa kita tidak tahu banyak tentang kekuatan sebenarnya dari sirkuit adalah karena kita tidak memiliki banyak contoh sirkuit minimum. Kita tidak tahu, misalnya, seperti apa rangkaian optimal untuk multiplikasi matriks Boolean. $3 \times 3$

Salah satu alasan bagus mengapa kita tidak tahu banyak tentang kekuatan sebenarnya dari sirkuit adalah bahwa kita tidak memiliki banyak contoh sirkuit minimum. Kita tidak tahu, misalnya, seperti apa rangkaian optimal untuk multiplikasi matriks Boolean. <...> Bisakah kita mendapat manfaat dari Ensiklopedia Sirkuit Minimum? Sebagai contoh, apa yang dilakukan sirkuit Boolean terkecil untuk $3 \times 3$ $10 \times 10$ Multiplikasi matriks Boolean terlihat seperti? Apakah strukturnya teratur? Sangat mungkin bahwa jawaban akan memberikan wawasan berharga tentang kompleksitas masalah. Algoritme terbaik yang kita tahu mengurangi masalah untuk perkalian matriks atas cincin, yang kemudian diselesaikan dengan konstruksi rekursif yang sangat teratur (seperti Strassen [Str69]). Bahkan jika sirkuit yang dikatalogkan tidak benar-benar minimal tetapi dekat dengan itu, contoh konkret untuk input kecil dapat berguna bagi ahli teori untuk menambang untuk inspirasi, atau mungkin untuk komputer untuk menambang untuk pola melalui teknik pembelajaran mesin. Kekuatan contoh-contoh kecil tidak bisa diremehkan.

Eksperimen dengan pemecah QBF belum mengungkapkan wawasan baru yang signifikan. Sejauh ini, mereka telah menemukan satu fakta: rangkaian ukuran optimal untuk perkalian matriks Boolean adalah yang jelas. Baiklah, duh. Bagaimana dengan case ? Ini sudah sulit! Solver sKizzo QBF [Ben05] dapat membuktikan bahwa tidak ada sirkuit untuk yang memiliki 10 gerbang, tetapi tidak ada yang lebih dari itu. Bahkan ketika kita membatasi gerbang untuk memiliki dua kipas, solver crash pada instance yang lebih besar. $2 \times 2$ $3 \times 3$ $3 \times 3$

Bersama dengan Evgeny Demenkov, Arist Kojevnikov, dan Grigory Yaroslavtsev kami berhasil menggunakan SAT-solver untuk meningkatkan batas atas pada ukuran sirkuit fungsi simetris. Detail dapat ditemukan dalam dua makalah berikut: Menemukan Sirkuit Efisien Menggunakan SAT-solver (2009), Batas Atas Baru pada Kompleksitas Sirkuit Boolean dari Fungsi Simetris (2010). Namun, kita tidak tahu kompleksitas rangkaian yang tepat untuk banyak fungsi dasar: misalnya, , .

2.5 n \leq C (M O D_{3}) \leq 3 n

$2.5n \le C(MOD_3) \le 3n$

2 n \leq C (A N D, O R, X O R) \leq 2.5 n

$2n \le C(AND,OR,XOR) \le 2.5n$

Latihan 477–481 dalam Bagian 7.2.2.2 : Kepuasan TAOCP Volume 4 oleh Don Knuth (2015) membahas cara menemukan sirkuit yang optimal dengan bantuan pemecah SAT. Dari solusi hingga latihan 481:

Itu benar untuk . Berikut ini adalah perhitungan 12 langkah ketika dan , ditemukan pada tahun 2014 oleh Armin Biere: <...> Kasing dan , yang terletak dekat dengan batas pemecah hari ini, masih belum diketahui . $n \le 5$ $n=6$ $a=0$ $n=6$ $a \neq 0$

Alexander S. Kulikov
sumber

5

Dalam banyak model tidak seragam - sirkuit Boolean, sirkuit aljabar, pohon keputusan, program percabangan, dll - menghitung kompleksitas yang tepat tampaknya jauh lebih sulit daripada menghitung kompleksitas asimptotik. Sementara saya mempertahankan harapan bahwa intuisi Anda benar - bahwa memahami kompleksitas yang tepat dari contoh kecil mungkin mengarah pada wawasan asimptotik - Saya tahu hanya beberapa kasus di mana ini terjadi:

Algoritma dan batas bawah untuk perkalian matriks format kecil. Ada cukup banyak pekerjaan pada 2x2 ( Strassen ), 3x3 ( Laderman ), dan format kecil lainnya untuk perkalian matriks (lihat juga Johnson-McLoughlin dan Hopcroft-Kerr ). Awalnya, ini sering dapat digunakan untuk memberikan perbaikan asimptotik, karena struktur rekursif multiplikasi matriks. Akhirnya, Coppersmith-Winograd menggantikan semua ini di ranah asimptotik.
Batas bawah gaya GCT pada perkalian matriks kecil karena Bürgisser dan Ikenmeyer telah menghasilkan batas bawah asimtotik pada perkalian matriks. Saya pikir ini setidaknya sebagian karena struktur representasi-teoretis secara alami menyarankan bagaimana mengubah batas bawah tunggal, tepat menjadi keluarga tanpa batas.
(Lihat jawaban Alexander Kulikov untuk lebih banyak pasangan)

Selain dari ini, ada sejumlah kecil tapi nontrivial pekerjaan pada kompleksitas yang tepat dari berbagai masalah, tetapi sebagian besar masalah lebih mudah daripada GraphIso atau Primes (kecuali untuk contoh terakhir dari permanen). Meskipun saya menemukan karya ini menarik dan mempertahankan harapan bahwa ini akan mengarah pada wawasan teoretis yang lebih besar, sejauh yang saya tahu belum melakukannya.

Knuth mempertimbangkan pertanyaan tentang jumlah persis perbandingan yang diperlukan untuk mengurutkan daftar elemen dalam Bab 5, Vol. 3 dari TAOCP . Kemajuan lebih lanjut telah dibuat sejak saat itu (lihat karya oleh Peczarski , dan referensi di dalamnya). $n$
Ada juga beberapa pekerjaan pada jaringan penyortiran kedalaman minimum yang tepat ( Bundala dan Závodný tampaknya menjadi yang terbaru).
Dengan kompleksitas yang tepat, dapat terjadi efek angka-teoretis karena ukuran input. (Ketika berhadapan dengan algoritma divide-and-conquer, misalnya, mudah untuk membayangkan bagaimana input dengan ukuran mungkin berbeda dari input dengan ukuran aneh ketika menyangkut kompleksitas yang tepat.) Lihat Drmota dan Szpankowski untuk contoh-contoh ini. , serta teorema master yang tepat. $2^k$
Kompleksitas determinan dari permanen kecil (terikat atas oleh B. Grenet dan baru-baru ini terikat pada oleh Alper, Bogart, dan Velasco ) dan fungsi lainnya ( Qiao, Sun, dan Yu ). $per_3$

Joshua Grochow
sumber

Kompleksitas sirkuit yang dihitung dari masalah keputusan

Jawaban: