Teorema Adleman atas semir tak terbatas?

Adleman telah menunjukkan pada tahun 1978 bahwa : jika fungsi boolean dari variabel dapat dihitung dengan rangkaian boolean probabilistik ukuran , maka dapat juga dihitung dengan deterministik sirkuit boolean polinomial ukuran dalam dan ; sebenarnya, dari ukuran . $\mathrm{BPP}\subseteq \mathrm{P/poly}$$f$$n$$M$$f$$M$$n$$O(nM)$

Pertanyaan Umum: Atas apa selain semiring (selain boolean) yang ditahan? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Untuk lebih spesifik, rangkaian probabilistic pada semiring menggunakan operasi "penjumlahan" dan "perkalian" sebagai gerbang Input adalah variabel input dan mungkin beberapa variabel acak tambahan, yang mengambil nilai dan secara independen dengan probabilitas ; di sini dan , masing-masing, identitas aditif dan multiplikatif dari semiring Sirkuit seperti itu menghitung fungsi yang diberikan$\mathsf{C}$$(S,+,\cdot,0,1)$$(+)$$(\cdot)$$x_1,\ldots,x_n$$0$$1$$1/2$$0$$1$$\mathsf{C}$ $f:S^n\to S$jika untuk setiap , . P r [ C ( x ) = f ( x ) ] ≥ 2 /$x\in S^n$$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$

Fungsi pemungutan suara dari variabel adalah fungsi parsial yang nilainya jika elemen muncul lebih dari kali di antara , dan tidak terdefinisi , jika tidak ada elemen seperti itu ada. Aplikasi sederhana batas Chernoff dan serikat pekerja menghasilkan yang berikut ini.m y y m / 2 y 1 , … , y m$\mathrm{Maj}(y_1,\ldots,y_m)$$m$$y$$y$$m/2$$y_1,\ldots,y_m$$y$

Trik Mayoritas: Jika rangkaian probabilistik menghitung fungsi pada himpunan terbatas , maka ada realisasi dari sehingga berlaku untuk semua x \ di x . f : S n → S X ⊆ S n m = O ( log | X | ) C 1 , … , C m C f ( x ) = M a j ( C 1 ( x ) , ... , C m ( x ) ) x ∈ $\mathsf{C}$$f:S^n\to S$$X\subseteq S^n$$m=O(\log|X|)$$C_1,\ldots,C_m$$\mathsf{C}$$f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$$x\in X$

Di atas semiring boolean, fungsi pemungutan suara $\mathrm{Maj}$ adalah fungsi mayoritas, dan memiliki sirkuit kecil (bahkan monoton). Jadi, teorema Adleman mengikuti dengan mengambil $X=\{0,1\}^n$ .

Tapi bagaimana dengan semir (terutama, tak terbatas) lainnya? Bagaimana dengan semiring aritmatika (dengan penambahan dan perkalian biasa)?$(\mathbb{N},+,\cdot,0,1)$

Pertanyaan 1: Apakah menahan semiring aritmatika? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Meskipun saya bertaruh untuk "ya", saya tidak bisa menunjukkan ini.

Catatan: Saya mengetahui makalah ini di mana penulis mengklaim atas bidang nyata . Mereka berurusan dengan sirkuit aritmatika non-monoton , dan juga tiba (dalam Teorema 4) ke sirkuit dengan fungsi pemungutan suara sebagai gerbang keluaran. Tetapi bagaimana mensimulasikan ini -gerbang oleh rangkaian aritmatika (apakah itu monoton atau tidak)? Yaitu cara mendapatkan akibat wajar 3 mereka? ( R , + , ⋅ , 0 , 1 ) M a j M a $\mathrm{BPP}\subseteq \mathrm{P/poly}$$(\mathbb{R},+,\cdot,0,1)$$\mathrm{Maj}$$\mathrm{Maj}$

Sebenarnya, argumen sederhana berikut yang disampaikan oleh Sergey Gashkov (dari Universitas Moskow) kepada saya tampaknya menunjukkan bahwa ini tidak mungkin (setidaknya untuk sirkuit yang hanya dapat menghitung polinomial ). Misalkan kita dapat mengekspresikan sebagai polinomial . Kemudian menyiratkan , menyiratkan , dan menyiratkan . Ini berlaku karena, lebih dari bidang karakteristik nol, persamaan fungsi polinomial berarti persamaan koefisien. Perhatikan bahwa dalam Pertanyaan 1, kisaran sirkuit probabilistik, dan karenanya, domainf ( x , y , z ) = a x + b y + c z + h ( x , y , z ) f ( x , x , z ) = x c = 0 f ( x , y , x ) = x b $\mathrm{Maj}(x,y,z)$$f(x,y,z)=ax+by+cz+ h(x,y,z)$$f(x,x,z)=x$$c=0$$f(x,y,x)=x$f ( x , y , y ) = y a = 0 M a $b=0$$f(x,y,y)=y$$a=0$$\mathrm{Maj}$ -gate tidak terbatas . Oleh karena itu saya memiliki kesan bahwa makalah terkait hanya berurusan dengan fungsi komputasi sirkuit aritmatika dengan rentang terbatas kecil , seperti . Maka memang mudah untuk dihitung oleh rangkaian aritmatika. Tetapi bagaimana jika ? Y Y = { 0 , 1 } M a j : Y m → Y Y = $f:\mathbb{R}^n\to Y$$Y$$Y=\{0,1\}$$\mathrm{Maj}:Y^m\to Y$$Y=\mathbb{R}$

---

Koreksi [6.03.2017]: Pascal Koiran (salah satu penulis makalah ini) menunjukkan kepada saya bahwa model mereka lebih kuat daripada hanya sirkuit aritmatika: mereka memungkinkan Gerbang Masuk (menghasilkan atau tergantung pada apakah input negatif dari tidak). Jadi, fungsi voting Maj dapat disimulasikan dalam model ini, dan saya mengambil kembali "kebingungan" saya.$0$$1$

---

Dalam konteks pemrograman dinamis, terutama yang menarik adalah pertanyaan yang sama untuk semir-minir plus- tropis dan max-plus dan (\ mathbb {N} \ cup \ {- \ infty \}, \ max, +, - \ infty, 0) .$(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$$(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$

Pertanyaan 2: Apakah berlaku untuk semir tropis? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Dimiliki dalam dua semiring ini, ini berarti bahwa keacakan tidak dapat mempercepat apa yang disebut algoritma pemrograman dinamis "murni"! Algoritma ini hanya menggunakan operasi Min / Max dan Sum dalam rekursi mereka; Bellman-Ford, Floyd-Warshall, Held-Karp, dan banyak algoritma DP terkemuka lainnya adalah murni. $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Sejauh ini, saya hanya dapat menjawab Pertanyaan 2 (secara afirmatif) di bawah skenario kesalahan satu sisi , ketika kami juga memerlukan atas min- ditambah semiring (minimalisasi), atau atas semiring max-plus (maksimalisasi). Artinya, kita sekarang mensyaratkan bahwa rangkaian tropis acak tidak pernah dapat menghasilkan lebih baik dari nilai optimal; Namun, hal itu dapat salah dengan memberikan beberapa nilai yang lebih buruk daripada yang optimal. Namun, pertanyaan saya ada di bawah skenario kesalahan dua sisi .$\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$$\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$

---

PS [ditambahkan 27.02.2017]: Ini adalah usaha saya untuk menjawab Pertanyaan 1 (dengan tegas). Idenya adalah untuk menggabungkan versi paling sederhana dari "Nullstellensatz" kombinatorial "dengan perkiraan untuk masalah Zarankiewicz untuk hypergrap n-partite, karena Erdos dan Spencer. Modulo hasil yang terakhir ini, seluruh argumen bersifat elementer.

Perhatikan bahwa Pertanyaan 2 masih tetap terbuka: "Null Nellstellensatz" (setidaknya dalam bentuk yang saya gunakan) tidak berlaku untuk semir tropis.

Ini hanya sebagian jawaban untuk pertanyaan umum Anda (saya tidak yakin apa formulasi yang sepenuhnya umum akan), tetapi itu menunjukkan bahwa bekerja dengan semir tak terbatas yang cukup bagus sambil membatasi keacakan ke domain yang terbatas mungkin sebenarnya meremehkan pertanyaan apakah Teorema Adleman berlaku.

Misalkan Anda sedang mengerjakan bilangan kompleks , sehingga sirkuit menghitung polinomial di atas bidang itu, dan anggap fungsi f itu sendiri dikomputasi oleh beberapa polinomial (betapapun rumit) dari variabel x . Kemudian ternyata sudah untuk beberapa r tetap , C ( x , r ) = f ( x ) . Alasannya adalah bahwa untuk setiap r , himpunan x dengan C ( x , r ) = f ( x ) menentukan subset Zariski-closed dari$\mathbb{C}$$f$$x$$r$$C(x,r) = f(x)$$r$$x$$C(x,r) = f(x)$ , dan jadi harus semua C n , atau bagian dari ukuran nol. Jika semua himpunan ini memiliki ukuran nol, maka, karena hanya ada banyakr yangdipertimbangkan, himpunanx dimana∃r:C(x,r)=f(x)juga memiliki ukuran nol. Di sisi lain, asumsi bahwaCmenghitungfmenyiratkan bahwa set harus semua C n , sehingga tidak dapat memiliki ukuran nol.$\mathbb{C}^n$$\mathbb{C}^n$$r$$x$$\exists r : C(x,r) = f(x)$$C$$f$$\mathbb{C}^n$