Adakah polinomial yang sulit dihitung tetapi mudah diputuskan?

Setiap rangkaian aritmatika monoton , yaitu sirkuit , menghitung beberapa polinomial F multivariat ( x 1 , … , x n ) dengan koefisien integer nonnegatif. Diberi polinom f ( x 1 , … , x n ) , sirkuit$\{+,\times\}$$F(x_1,\ldots,x_n)$$f(x_1,\ldots,x_n)$

• Toedjoe menghitung jika F ( a ) = f ( a ) berlaku untuk semua a ∈ N n ; $f$$F(a)=f(a)$$a\in \mathbb{N}^n$
• jumlah jika F ( a ) = f ( a ) berlaku untuk semua a ∈ { 0 , 1 } n ; $f$$F(a)=f(a)$$a\in\{0,1\}^n$
• memutuskan jika F ( a ) > 0 persis ketika f ( a ) > 0 berlaku untuk semua a ∈ { 0 , 1 } n . $f$$F(a)>0$$f(a)>0$$a\in\{0,1\}^n$

Saya tahu polinomial eksplisit (bahkan multilinear) yang menunjukkan bahwa celah ukuran sirkuit "menghitung / menghitung" dapat bersifat eksponensial. Pertanyaan saya menyangkut jeda "jumlah / keputusan".$f$

Pertanyaan 1: Apakah ada yang tahu tentang polinomial yang secara eksponensial lebih sulit untuk dihitung daripada memutuskan dengan { + , × } -circuits? $f$$\{+,\times\}$

Sebagai kandidat yang memungkinkan, seseorang dapat mengambil polinomial PATH yang variabelnya sesuai dengan tepi grafik lengkap pada { 1 , … , n } , dan masing-masing monomial berhubungan dengan jalur sederhana dari simpul 1 ke simpul n dalam K n . Polinomial ini dapat diputuskan oleh rangkaian ukuran O ( n 3 ) yang mengimplementasikan, katakanlah, algoritma pemrograman dinamis Bellman-Ford, dan relatif mudah untuk menunjukkan bahwa setiap komputasi sirkuit sirkuit { + , × $K_n$$\{1,\ldots,n\}$$1$$n$$K_n$$O(n^3)$$\{+,\times\}$PATH harus berukuran . $2^{\Omega(n)}$

Di sisi lain, setiap rangkaian penghitungan PATH memecahkan yang masalah PATH, yaitu menghitung jumlah 1 -to- n jalan di ditentukan oleh yang sesuai 0 - 1 subgraf masukan dari K n . Ini adalah masalah yang disebut # P -lengkap . Jadi, kita semua "percaya" bahwa PATH tidak dapat memiliki penghitungan { + , × } -circuit dengan ukuran polinomial. Masalah "hanya" adalah untuk membuktikan ini ... $\#$$1$$n$$0$$1$$K_n$$\#$$\{+,\times\}$

Saya dapat menunjukkan bahwa setiap -circuit yang menghitung jalur polinomial jalur Hamiltonian terkait memerlukan ukuran eksponensial. Monomials dari bersesuaian ini polinomial untuk 1 -to- n jalan di K n mengandung semua node. Sayangnya, pengurangan dari # HP untuk # PATH oleh Valiant membutuhkan untuk menghitung invers dari matriks Vandermonde, dan karenanya tidak dapat dilaksanakan oleh { + , × } -circuit.$\{+,\times\}$$1$$n$$K_n$$\#$$\#$$\{+,\times\}$

Pertanyaan 2: Apakah ada yang melihat pengurangan # HP menjadi # PATH secara monoton ? $\#$$\#$

Dan akhirnya:

Pertanyaan 3: Apakah "versi monoton" kelas P dipertimbangkan? $\#$

NB Perhatikan bahwa saya berbicara tentang kelas sirkuit yang sangat terbatas: sirkuit aritmatika monoton ! Di kelas -circuits, Pertanyaan 1 tidak adil untuk ditanyakan sama sekali: tidak ada batas bawah yang lebih besar dari Ω ( n log n ) untuk sirkuit seperti itu, bahkan ketika diminta untuk menghitung polinomial tertentu pada semua input dalam R n , diketahui. Juga, di kelas sirkuit seperti itu, "analog struktural" dari Pertanyaan 1 - apakah ada # P- polinomial lengkap yang dapat diputuskan dengan poly-size { + , $\{+,-,\times\}$$\Omega(n\log n)$$\mathbb{R}^n$$\#$ -lingkaran? - Memiliki jawaban afirmatif. Seperti adalah, misalnya, PER polinomial permanen = Σ h ∈ S n Π n i = 1 x i , h ( i ) . $\{+,-,\times\}$$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$

TAMBAH: Tsuyoshi Ito menjawab Pertanyaan 1 dengan trik yang sangat sederhana. Tetap saja, Pertanyaan 2 dan 3 tetap terbuka. Status penghitungan PATH menarik karena keduanya merupakan masalah DP standar dan karena # P-complete.

(Saya memposting komentar saya sebagai jawaban untuk menanggapi permintaan OP.)

Adapun Pertanyaan 1, biarkan f _n : {0,1} ⁿ → ℕ menjadi keluarga fungsi yang sirkuit aritmatika membutuhkan ukuran eksponensial. Maka demikian juga f _n 1, tapi f _n 1 mudah untuk memutuskan dengan sirkuit aritmatika sepele monoton. Jika Anda memilih untuk menghindari konstanta dalam monoton sirkuit aritmatika, maka biarkan f _n : {0,1} ⁿ → ℕ menjadi keluarga fungsi sehingga sirkuit aritmatika untuk f _n membutuhkan ukuran eksponensial dan f _n (0, ..., 0) = 0, dan pertimbangkan f _n + x ₁ + ... + x _n .