Tes identitas acak untuk polinomial tingkat tinggi?

Misalkan adalah -variate polinomial yang diberikan sebagai rangkaian aritmatika dengan ukuran poli , dan misalkan menjadi bilangan prima. $f$ $n$ $(n)$ $p = 2^{\Omega(n)}$

Bisakah Anda menguji apakah identik nol lebih dari , dengan waktu dan probabilitas kesalahan , bahkan jika derajatnya tidak apriori terikat? Bagaimana jika adalah univariat? $f$ $\mathbb{Z}_p$ $\mbox{poly}(n)$ $\leq 1-1/\mbox{poly}(n)$ $f$

Perhatikan bahwa Anda dapat menguji secara efisien apakah identik nol sebagai ekspresi formal , dengan menerapkan Schwartz-Zippel pada bidang ukuran katakanlah , karena tingkat maksimum adalah . $f$ $2^{2|f|}$ $f$ $2^{|f|}$

polynomials arithmetic-circuits pengguna94741
sumber

jika Anda tidak memiliki batasan pada tingkat, bukankah ada polinomial yang menyadari fungsi tertentu?

Peter Shor

@PeterShor:

$\:$ OP memang memiliki batas derajat; tidak boleh lebih dari 2 hingga [jumlah gerbang di

f

$\hspace{.04 in}f\hspace{.02 in}$ ]

$\;\;\;\;$

Saya berpikir bahwa poin penting dari pertanyaan ini adalah bahwa bidang GF (p) tidak cukup besar untuk menggunakan lem Schwartz-Zippel untuk membangun algoritma waktu polinomial acak dalam cara standar, atau cukup kecil (seperti GF (2) ) untuk menggunakan arithmetization untuk membangun pengurangan dari SAT dengan cara standar.

Tsuyoshi Ito

Dalam kasus univariat, pertanyaan bertanya apakah

membagi

, yang dapat diperiksa dalam bidang yang lebih besar jika itu membantu. Tidak yakin apakah itu digeneralisasikan ke multivarian.

x^{p} - 1

$x^p-1$

f

$f$

Geoffrey Irving

@ GeoffreyIrving Terima kasih! Apakah mudah untuk memeriksa secara efisien

kapan

diberikan sebagai sirkuit?

(x^{p} - 1) | f

$(x^p - 1) | f$

f

$f$

user94741

Tidak jelas bagi saya apa input dari masalah dan bagaimana Anda menegakkan pembatasan , namun, dalam rumusan yang masuk akal jawabannya adalah tidak untuk polinomial multivariat kecuali NP = RP, karena pengurangan di bawah. $p=2^{\Omega(n)}$

Mengingat kekuatan prima dalam biner dan Boolean sirkuit (wlog hanya menggunakan dan gerbang), kita dapat membangun dalam waktu polinomial sirkuit aritmatika sehingga adalah unsatisfiable IFF menghitung sebuah identik nol polinomial lebih sebagai berikut: menerjemahkan dengan , dengan , dan variabel dengan $q$ $C$ $\land$ $\neg$ $C_q$ $C$ $C_q$ $\mathbb F_q$ $a\land b$ $ab$ $\neg a$ $1-a$ $x_i$ $x_i^{q-1}$ (yang dapat diekspresikan oleh rangkaian ukuran menggunakan kuadrat ulang). $O(\log q)$

Jika adalah prima (yang saya tidak berpikir benar-benar penting) dan cukup besar, kita bahkan bisa membuat univariat pengurangan: memodifikasi definisi sehingga diterjemahkan dengan polinomial Di satu sisi, $q=p$ $C_p$ $x_i$

f_{i} (x) = ((x + i)^{(p - 1) / 2} + 1)^{p - 1} .

$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$

untuk setiap

, maka jika

adalah unsatisfiable, maka

untuk setiap

. Di sisi lain, asumsikan bahwa

memuaskan, katakanlah

, di mana

. Perhatikan bahwa

f_{i} (a) \in {0, 1}

$f_i(a)\in\{0,1\}$

a \in F_{p}

$a\in\mathbb F_p$

C

$C$

C_{p} (a) = 0

$C_p(a)=0$

a

$a$

C

$C$

C (b_{1}, \dots, b_{n}) = 1

$C(b_1,\dots,b_n)=1$

b_{i} \in {0, 1}

$b_i\in\{0,1\}$

Dengan demikian, kita memiliki

jika

adalah seperti yang

f_{i} (a) = {\begin{cases} 1 & if a + i is a quadratic residue (including 0), \\ 0 & if a + i is a quadratic nonresidue. \end{cases}

$f_i(a)=\begin{cases}1&\text{if $a+i$ is a quadratic residue (including $0$),}\\ 0&\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$

C_{p} (a) = 1

$C_p(a)=1$

a \in F_{p}

$a\in\mathbb F_p$

untuk setiap

. Akibat wajar 5 diPeraltamenyiratkan bahwa seperti

selalu ada untuk

Sebuah + saya adalah residu kuadratik ⟺ b_{saya} = 1

$a+i\text{ is a quadratic residue }\iff b_i=1$

i = 1, \dots, n

$i=1,\dots,n$

a

$a$

p \geq (1 + o (1)) 2^{2 n} n^{2}

$p\ge(1+o(1))2^{2n}n^2$

Emil Jeřábek
sumber

Pengurangan univariat sebenarnya bekerja untuk nonprima

juga, asalkan itu aneh (dan orang mungkin dapat menangani kekuatan

dengan cara lain). Alih-alih konstanta

, seseorang dapat mengambil urutan tetap dari

elemen yang berbeda dari lapangan; yang diperlukan

lagi ada jika

oleh dasarnya argumen yang sama seperti pada kertas Peralta ini (kerja nyata di Weil terikat pada jumlah karakter, yang berlaku untuk semua bidang terbatas).

q

$q$

2

$2$

1, \dots, n

$1,\dots,n$

n

$n$

a

$a$

q \geq 2^{2 n} n^{2}

$q\ge2^{2n}n^2$

Emil Jeřábek

Ah, ya: jika

, kita dapat memperbaiki

-linearly independent

, dan menerjemahkan

dengan

, di mana

adalah jejak

q = 2^{k} \geq 2^{n}

$q=2^k\ge2^n$

F_{2}

$\mathbb F_2$

{a_{i} : i = 1, \dots, n} \subseteq F_{q}

$\{a_i:i=1,\dots,n\}\subseteq\mathbb F_q$

x_{i}

$x_i$

T (a_{i} x)

$T(a_ix)$

T (x) = \sum_{j < k} x^{2^{j}}

$T(x)=\sum_{j<k}x^{2^j}$

F_{q} / F_{2}

$\mathbb F_q/\mathbb F_2$

Emil Jeřábek

Tes identitas acak untuk polinomial tingkat tinggi?

Jawaban: