Sirkuit aritmatika monoton

Keadaan pengetahuan kita tentang sirkuit aritmatika umum tampaknya mirip dengan keadaan pengetahuan kita tentang sirkuit Boolean, yaitu kita tidak memiliki batas bawah yang baik. Di sisi lain, kami memiliki batas bawah ukuran eksponensial untuk sirkuit Boolean monoton .

Apa yang kita ketahui tentang sirkuit aritmatika monoton ? Apakah kita memiliki batas bawah yang sama baik untuk mereka? Jika tidak, apa perbedaan penting yang tidak memungkinkan kita untuk mendapatkan batas bawah yang serupa untuk sirkuit aritmatika monoton?

Pertanyaannya terinspirasi oleh komentar pada pertanyaan ini .

Batas bawah untuk sirkuit aritmatika monoton lebih mudah karena mereka melarang pembatalan. Di sisi lain, kita dapat membuktikan batas bawah eksponensial untuk sirkuit komputasi fungsi boolean bahkan jika ada monoton bernilai real fungsi diperbolehkan sebagai gerbang (lihat misalnya Sekte 9.6 di. Buku ).$g:R\times R\to R$

$a\land a=a$$a\lor (a\land b)=a$$(+,\min)$$(+,\max)$. Gates kemudian berhubungan dengan submasalah yang digunakan oleh algoritma. Apa Jerrum dan Snir (dalam makalah oleh V Vinay) benar-benar membuktikan adalah bahwa algoritma DP apa pun untuk Min Weight Perfect Matching (serta untuk masalah TSP) harus menghasilkan banyak subproblem secara eksponensial. Tetapi masalah Perfect Mathching bukan dari "DP flawor" (itu tidak memenuhi Prinsip Optimalitas Bellman ). Pemrograman linier (bukan DP) jauh lebih cocok untuk masalah ini.

Jadi bagaimana dengan masalah optimasi yang dapat diselesaikan dengan algoritma DP yang cukup kecil - dapatkah kita membuktikan batas bawah juga untuk mereka? Sangat menarik dalam hal ini adalah hasil lama dari Kerr (Teorema 6.1 dalam PhD- nya ). Ini menyiratkan bahwa algoritma DP Floyd-Warshall klasik untuk masalah All-Pairs Shortest Paths (APSP) optimal : subproblem diperlukan. Yang lebih menarik adalah bahwa argumen Kerr sangat sederhana (jauh lebih sederhana daripada yang digunakan Jerrum dan Snir): argumen ini hanya menggunakan aksioma distributivitas , dan kemungkinan untuk "membunuh" gerbang kecil dengan menetapkan salah satu argumennya ke Dengan cara ini ia membuktikan bahwa$\Omega(n^3)$$a+\min(b,c)=\min(a,b)+\min(a,c)$$0$$n^3$gerbang plus diperlukan untuk mengalikan dua matriks selama semiring . Serangga. 5.9 dari buku oleh Aho, Hopcroft dan Ullman ditunjukkan bahwa masalah ini setara dengan masalah APSP.$n\times n$$(+,\min)$

Pertanyaan selanjutnya adalah: bagaimana dengan masalah Single-Source Shortest Paths (SSSP)? Algoritma Bellman-Ford DP untuk masalah ini (tampaknya "lebih sederhana") juga menggunakan gerbang . Apakah ini optimal? Sejauh ini, tidak ada pemisahan antara dua versi dari masalah jalur terpendek ini yang diketahui; lihat kertas Virginia dan Ryan Williams yang menarik di sepanjang baris ini. Jadi, rangkaian lebih rendah di dalam -sirkuit untuk SSSP akan menjadi hasil yang bagus. Pertanyaan selanjutnya bisa: bagaimana dengan batas bawah untuk Knapsack? Dalam konsep ini, batas bawah untuk Knapsack terbukti dalam model sirkuit lebih lemah di mana penggunaanΩ ( n 3 ) ( + , min ) ( + , maks ) $O(n^3)$$\Omega(n^3)$$(+,\min)$$(+,\max)$$+$- gerbang dibatasi; dalam Lampiran bukti Kerr direproduksi.

Iya nih. Kami tahu batas bawah yang baik dan kami sudah mengenalnya cukup lama sekarang.

Jerrum dan Snir membuktikan batas bawah eksponensial atas sirkuit aritmatika monoton untuk permanen pada tahun 1980. Valiant menunjukkan bahkan gerbang minus tunggal secara eksponensial lebih kuat .

Untuk informasi lebih lanjut tentang sirkuit aritmatika (monoton), lihat survei Shpilka tentang sirkuit aritmatika.

Hasil lain yang saya sadari adalah oleh Arvind, Joglekar dan Srinivasan - mereka menghadirkan polinomial eksplisit yang dapat dihitung dengan sirkuit aritmatika monoton ukuran lebar linier tetapi sirkuit aritmetika monoton lebar akan mengambil ukuran eksponensial.$2k$$k$

Apakah ini diperhitungkan: Batas bawah semi-grup Chazelle untuk masalah pencarian rentang mendasar (dalam pengaturan offline). Semua batas bawah hampir optimal (hingga istilah log ketika batas bawah adalah polinomial dan istilah log log ketika batas bawah adalah polylogarithmic).