Teste de identidade randomizado para polinômios de alto grau?

Seja um polinômio variável, dado como um circuito aritmético de tamanho poli , e seja um primo. $f$ $n$ $(n)$ $p = 2^{\Omega(n)}$

Você pode testar se $f$ é igual a zero acima de $\mathbb{Z}_p$ , com time $\mbox{poly}(n)$ e probabilidade de erro $\leq 1-1/\mbox{poly}(n)$ , mesmo que o grau não seja a priori delimitado? E se $f$ for univariado?

Observe que você pode testar com eficiência se $f$ é identicamente zero como expressão formal , aplicando Schwartz-Zippel sobre um campo de tamanho, digamos , porque o grau máximo de é . $2^{2|f|}$ $f$ $2^{|f|}$

polynomials arithmetic-circuits user94741
fonte

se você não tem limites no grau, não há um polinômio que realize alguma função específica?

Peter Shor

@PeterShor:

$\:$ O OP não têm um limite no grau; não pode ser maior que 2 para [o número de portas no

f

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

$\;\;\;\;$

Penso que o ponto crucial desta questão é que o campo GF (p) não é grande o suficiente para usar o lema de Schwartz – Zippel para construir um algoritmo de tempo polinomial aleatório de maneira padrão, nem suficientemente pequeno (como GF (2) ) para usar a aritmetização para construir uma redução do SAT de maneira padrão.

Tsuyoshi Ito 22/10

No caso univariado, a pergunta pergunta se divide , que pode ser verificado em um campo maior, se isso ajudar. Não tenho certeza se isso generaliza para multivariada.

x^{p} - 1

$x^p-1$

f

$f$

Geoffrey Irving

@GeoffreyIrving Thanks! É fácil verificar com eficiência quando é dado como um circuito?

(x^{p} - 1) | f

$(x^p - 1) | f$

f

$f$

user94741

Não está exatamente claro para mim qual é a entrada do problema e como você impõe a restrição , no entanto, sob qualquer formulação razoável, a resposta é não para polinômios multivariados, a menos que NP = RP, devido à redução abaixo. $p=2^{\Omega(n)}$

Dada uma potência principal no binário e no circuito booleano (wlog usando apenas portas e ), podemos construir em tempo polinomial um circuito aritmético modo que seja insatisfatório se um polinômio idêntico zero sobre da seguinte maneira: traduza com , com e uma variável com (que pode ser expressa por um circuito do tamanho usando o quadrado repetido ) $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}$ $O(\log q)$

Se é primo (o que eu acho que realmente não importa) e suficientemente grande, podemos até tornar a redução univariada: modifique a definição de para que seja traduzido com o polinômio Por um lado, para cada , portanto, se for insatisfatório, para cada . Por outro lado, suponha que seja satisfatório, diga , onde . Notar que $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}.$

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\}$

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}$ Assim, temos se é tal que para cada . Corolário 5 em Peralta implica que tais sempre existe para .

C_{p} (a) = 1

$C_p(a)=1$

a \in F_{p}

$a\in\mathbb F_p$

uma + Eu is a quadratic residue ⟺ b_{i} = 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
fonte

A redução univariada também funciona para primário , desde que seja ímpar (e provavelmente é possível lidar com potências de de outra maneira). Em vez das constantes , pode-se pegar qualquer sequência fixa de elementos distintos do campo; o necessário existe novamente se , essencialmente pelo mesmo argumento do artigo de Peralta (o trabalho real está no Weil vinculado às somas de caracteres, o que vale para todos os campos finitos).

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 Jerabek

Ah, sim: se , podemos corrigir linearmente independente e traduzir com , em que é o rastreio de .

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 Jerabek

Teste de identidade randomizado para polinômios de alto grau?

Respostas: