Mengapa gerbang mod_m menarik?

Ryan Williams baru saja memposting batas bawahnya pada ACC , kelas masalah yang memiliki sirkuit kedalaman konstan dengan fan-in dan gerbang tanpa batas DAN, ATAU, BUKAN dan MOD_m untuk semua kemungkinan yang ada.

Apa yang istimewa dari gerbang MOD_m?

• Mereka memungkinkan seseorang untuk mensimulasikan aritmatika pada cincin Z_m apa pun.
• Sebelum hasil Ryan, melemparkan gerbang MOD_m ke campuran memberi kelas pertama yang batas bawah yang diketahui tidak bekerja.

Apakah ada alasan alami lain untuk mempelajari gerbang MOD_m?

$ACC^0$ adalah kelas kompleksitas alami.

1) Barrington menunjukkan bahwa perhitungan monoid yang tidak dapat dipecahkan menangkap $NC^1$ sedangkan monoid yang dapat dipecahkan menangkap $ACC^0$ .

2) Baru-baru ini, Hansen dan Koucky terbukti hasil indah yang poli berukuran konstan lebar program bercabang planar yang persis $ACC^0$ . Tanpa syarat planaritas, kami tentu saja mendapatkan hasil Barrington yang mengkarakterisasi $NC^1$ .

Jadi perbedaan antara dan N C 1 adalah teori grup di satu sisi dan topologi di sisi lain.$ACC^0$$NC^1$

Ditambahkan: Dana, contoh sederhana dari grup yang dapat dipecahkan adalah , grup simetris di atas elemen. Tanpa merinci, setiap kelompok yang dapat dipecahkan memiliki seri yang perundingannya bersifat siklik. Struktur siklik ini akan dipantulkan sebagai gerbang mod saat membangun sirkuit untuk menyelesaikan masalah kata pada grup.$S_4$

Pada planaritas, orang ingin percaya bahwa planaritas dapat memaksakan pembatasan / hambatan dalam arus informasi. Ini tidak selalu benar: misalnya, variasi planar 3SAT dikenal sebagai NP-complete. Namun, di kelas yang lebih kecil, pembatasan ini lebih "cenderung" berlaku.

Dalam nada yang sama, Wigderson menunjukkan NL / poli = UL / poli menggunakan lemma isolasi. Kami tidak tahu bagaimana cara derandomisasi lemma isolasi atas DAG sewenang-wenang untuk mendapatkan NL = UL, tetapi kami tahu bagaimana melakukannya untuk DAG planar.

$\bmod m$$m$$\bmod p$

$\bmod p$$\mathbb{F}_p$$n$

$\bmod m$$m$$2$

$AC^0[\bmod 6]$

Hanya untuk menguraikan dua poin Anda:

Jika kita berada dalam bisnis memahami komputasi, penghitungan modular adalah salah satu batas pemahaman kita. Penghitungan modular adalah salah satu fenomena paling sederhana dan paling alami dalam perhitungan, namun kita tampaknya hanya mengerti sedikit tentangnya. Kami tidak dapat mengesampingkan kemungkinan bahwa sirkuit ukuran 3 polinomial dengan hanya gerbang Mod6 dapat menghitung setiap fungsi dalam NP. Namun diduga bahwa sirkuit seperti itu hanya dapat menghitung fungsi dengan ukuran dukungan besar dan karenanya tidak dapat menghitung fungsi yang sangat sederhana seperti DAN. Pada sisi batas atas situasinya serupa, kami tidak memiliki hasil yang tidak sepele.

Pertanyaan-pertanyaan ini juga sangat menarik dari perspektif matematika murni karena mereka terkait erat dengan pertanyaan yang sangat alami tentang polinomial dan matriks lebih dari Z_m. Untuk memberikan satu contoh, kami tidak memiliki batas bawah yang baik untuk peringkat matriks codiagonal nxn di atas Z_6. Matriks codiagonal memiliki 0 pada diagonal dan nonzeros off diagonal.