Kompleksitas pengujian untuk nilai versus komputasi suatu fungsi

Secara umum kita tahu bahwa kompleksitas pengujian apakah suatu fungsi mengambil nilai tertentu pada input yang diberikan lebih mudah daripada mengevaluasi fungsi pada input tersebut. Sebagai contoh:

• Mengevaluasi permanen dari matriks integer nonnegatif adalah # P-hard, namun mengatakan apakah permanen itu nol atau bukan nol dalam P (pencocokan bipartit)

• Ada n bilangan real , sedemikian sehingga polinomial memiliki properti berikut (memang sebagian besar set bilangan real akan memiliki properti ini) . Untuk input diberikan , menguji apakah polinomial ini nol atau tidak mengambil perkalian dan perbandingan (berdasarkan hasil Ben-Or , karena set nol memiliki komponen), tetapi mengevaluasi polinomial di atas membutuhkan setidaknya langkah-langkah, oleh Paterson-Stockmeyer .∏ n i = 1 ( x - a i ) n x Θ ( log n $a_1,...,a_n$$\prod_{i=1}^{n}(x - a_i)$$n$$x$$\Theta(\log n)$Ω ( $n$$\Omega(\sqrt{n})$

• Penyortiran membutuhkan langkah-langkah pada pohon perbandingan (juga langkah-langkah pada pohon keputusan aljabar nyata, lagi dengan hasil Ben-Or), tetapi pengujian jika daftar diurutkan hanya menggunakan perbandingan .Ω ( n log n ) n - $\Omega(n \log n)$$\Omega(n \log n)$$n-1$

Adakah kondisi umum pada polinomial yang cukup untuk menyatakan bahwa kompleksitas (aljabar) pengujian apakah polinomial nol atau tidak sama dengan kompleksitas evaluasi polinomial?

Saya mencari kondisi yang tidak tergantung pada mengetahui kompleksitas masalah sebelumnya.

( Klarifikasi 10/27/2010 ) Agar lebih jelas, polinomial bukan bagian dari input. Apa itu artinya, mengingat kumpulan fungsi tetap (satu untuk setiap ukuran input (baik bitlength atau jumlah input)), saya ingin membandingkan kompleksitas masalah bahasa / keputusan dengan kompleksitas mengevaluasi fungsi .$\{ f_n \}$ $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ $\{f_n\}$

Klarifikasi: Saya bertanya tentang kompleksitas asimptotik dalam mengevaluasi / menguji keluarga polinomial. Misalnya, pada bidang tetap (atau cincin, seperti $\mathbb{Z}$ ) "permanen" bukan polinom tunggal, tetapi keluarga tak terbatas $\{perm_{n} : n \geq 0 \}$ mana $perm_{n}$ adalah permanen dari sebuah matriks $n \times n$ atas bidang itu (atau cincin).

Selama , pengujian untuk nol dan evaluasi adalah "hampir" sama dalam arti berikut: Asumsikan Anda memiliki pohon keputusan yang tes apakah beberapa tereduksi polinomial f yaitu nol. Kami bekerja di atas C , oleh karena itu kami hanya dapat menguji kesetaraan tetapi kami tidak memiliki "<". Itulah perbedaan penting dari contoh kedua dalam pertanyaan! Sekarang ambil jalur tipikal, yaitu jalur yang diambil oleh hampir semua input (kita selalu mengikuti cabang " ≠ "). Selanjutnya, ambil jalur tipikal semua elemen dalam varietas V ( f ) . Biarkan v menjadi simpul di mana kedua jalur ini mengambil cabang yang berbeda untuk pertama kalinya. Biarkan h 1$\mathbb{C}$$f$$\mathbb{C}$$\not=$$V(f)$$v$ menjadi polinomial yang diuji di sepanjang awalan umum dari dua jalur. Karena V ( f ) ditutup, semua elemen yang terletak di V ( f ) dan jangkauan v juga terletak di V ( h m ) . Oleh karena itu, jika f ( x ) = 0 , maka salah satu dari h i menghilang pada x . Kami menerapkan Hilbert Nullstellensatz untuk h 1 ⋯ h m dan mendapatkan bahwa f g $h_1,\dots,h_m$$V(f)$$V(f)$$v$$V(h_m)$$f(x) = 0$$h_i$$x$$h_1 \cdots h_m$ untuk beberapa polinomial g yang ini coprime untuk f . Singkatnya, ketika kita tidak menghitung f , ketika memutuskan apakah f ( x ) = 0 , kita harus menghitung f g untuk beberapa koprime g .$f g = h_1 \cdots h_m$$g$$f$$f$$f(x) = 0$$fg$$g$

"Penggunaan Algorithmic dari Feferman-Vaught Theorem" karya Makowski mungkin relevan. Dia mendefinisikan polinomial dengan menjumlahkan struktur yang dapat didefinisikan MSOL pada grafik dan menunjukkan bahwa mereka dapat ditelusuri untuk mengevaluasi ketika grafik dibatasi oleh lebar pohon.

Ini tidak banyak bicara tentang perbedaan dalam kompleksitas pengujian / evaluasi selain FPT. Menguji suatu nilai berarti menanyakan apakah ada seting variabel sedemikian sehingga diberikan rumus MSO2 pada grafik yang diberikan bernilai true, sedangkan evaluasi melibatkan penghitungan tugas yang memuaskan dari rumus MSO2. Ini tampaknya terkait dengan pertanyaan tentang bagaimana kompleksitas penghitungan SAT terkait dengan kompleksitas SAT.

Sunting 10/29 Konsep lain yang berguna mungkin untuk melihat ke Properti Uniform Difficult Point. Tampaknya polinomial dengan properti ini mudah dievaluasi di semua titik, atau sulit dievaluasi hampir di setiap titik. Makowski memberikan beberapa referensi tentang slide 46-52 - http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf

Aku akan menjelajah gagasan bahwa mengevaluasi polinomial di F p untuk tetap prima p (atau ekstensi lapangan terbatas daripadanya, dan dengan koefisien terbatas pada bidang yang sama) akan cocok kriteria Anda.$q(x)$$\mathbb F_p$$p$

lebih konkretnya, mari kita pertimbangkan polinomial dalam . Kita tahu bahwa x 2 = x dalam F 2 , jadi jika kita mengasumsikan bahwa setiap polinomial sudah dalam bentuk tereduksi ketika diberikan sebagai input, kita tinggal mempertimbangkan salah satu dari: 0 , 1 , x , x + 1 dan karenanya mengevaluasi semua polinomial ini pada 0 atau 1 membutuhkan paling banyak 2 operasi aritmatika.$\mathbb F_2[x]$$x^2=x$$\mathbb F_2$$0,1,x,x+1$$0$$1$

Saya percaya bahwa pernyataan "waktu konstan melalui operasi aritmatika tetap" yang serupa berlaku lebih umum untuk mana q = p n di mana p adalah prima. perhatikan bahwa jika n tidak diperbaiki, pernyataan ini tidak lagi valid$\mathbb F_q$$q=p^n$$p$$n$

Saya tidak yakin apakah saya memahami pertanyaan dengan benar, tetapi izinkan saya mencoba menjelaskan.

Biasanya, mengevaluasi polinomial pada nilai-nilai tertentu lebih mudah daripada pengujian identitas, terutama ketika representasi polinomial adalah melalui rangkaian (beberapa representasi ringkas). Namun, ada banyak algoritma pengujian identitas acak ( Schwarz-Zippel menjadi yang paling mudah) yang bekerja hanya pada evaluasi.

Dalam kasus khusus tertentu, kami memiliki tes 'kotak hitam' untuk pengujian identitas di mana Anda dapat menguji apakah polinomialnya nol atau tidak dengan hanya mengevaluasinya pada set poin yang telah ditentukan. Contoh sederhananya adalah jika polinomialnya 'jarang' (hanya memiliki monomial). Untuk membuat eksposisi lebih sederhana, mari kita asumsikan polinomialnya multilinear (setiap monomial adalah produk dari variabel yang berbeda).$n^{O(1)}$

Cara alami untuk mengirim polinomial multilinear multivariat ke univariat adalah melalui substitusi . Polinomial yang dihasilkan adalah ∑ i ∈ S α i y a i . Tentu saja ini bisa menjadi polinomial derajat eksponensial, tetapi mari kita lanjutkan modulo y r - 1 untuk sejumlah kecil r 's. Sekarang r akan menjadi "buruk" untuk sepasang monomial jika y a dan y b dipetakan ke modulo monomial yang sama y r - $x_i \mapsto y^{2^i}$$\sum_{i\in S} \alpha_i y^{a_i}$$y^r - 1$$r$$r$$y^a$$y^b$$y^r - 1$. Atau dengan kata lain, membagi a - b . Jadi selama r tidak membagi ∏ i , j ∈ S ( a i - a j ) , ini tidak akan terjadi. Oleh karena itu cukup untuk menjalankan rentang polinomial r 's. Dengan demikian, cukup untuk mengevaluasi polinomial pada beberapa akar persatuan dan kita dapat mengetahui polinomialnya nol atau tidak.$r$$a - b$$r$$\prod_{i,j\in S} (a_i - a_j)$$r$

Telah ada lebih banyak kemajuan dalam algoritma pengujian identitas kotak hitam. Saat ini, sebagian besar berdiri pada kedalaman 3 sirkuit terbatas (jumlah produk dari jumlah variabel). (FWIW) Beberapa dari ini disebutkan secara lebih rinci dalam Bab 3 dan 4 dari tesis M.Sc saya . Dan ada perbaikan lebih lanjut oleh Saxena dan Seshadri baru-baru ini juga.

Masalah #P, atau bahkan # P / poly, dapat ditulis sebagai polinomial: buat sirkuit dari gerbang NAND, tulis ini sebagai mana x dan y adalah bilangan bulat bernilai 0-1, dan jumlah semua input . Hal ini memberikan polinomial dalam Z [ x 1 , . . . , x n ] untuk input ukuran n . Masalah keputusan sedang menguji apakah ini 0.$1-xy$$x$$y$$\mathbb{Z}[x_1,...,x_n]$$n$