Siguiente: Método de Monte-Carlo para Un nivel arriba: Expresiones polinomiales nulas Anterior: Expresiones polinomiales nulas

.

El problema se resuelve probabilísticamente por el algoritmo siguiente:

1234567890123456789012345678901234567890 $N:=2\cdot \partial E$
; 

Choose m integer vectors $\{\mbox{\bf x}_1,\ldots,\mbox{\bf x}_m\}\subset [1,N]^m$
; 

		 if $\bigwedge_{i=1}^m(E(\mbox{\bf x}_i)=0)$
then ``Yes'' else ``No'' 

Si la entrada E es efectivamente nula el algoritmo responde correctamente. Si E no es nula el algoritmo responde equivocadamente, con una probabilidad pequeña, la de elegir precisamente m raices de E en un conjunto con $2^m\cdot (\partial E)^m$ puntos, la cual probabilidad es, en todo caso, menor que $\frac{1}{2}$. La probabilidad de error puede disminuirse arbitrariamente reiterando la selección de puntos de prueba:

1234567890123456789012345678901234567890 $N:=2\cdot \partial E$
; 

		 $\mbox{\rm Flag} :=\mbox{\it True}$
; $\mbox{\rm ntimes}:=1$
; 

		 while $\mbox{\rm Flag}\land (\mbox{\rm ntimes}\leq t)$
do { 

Choose m integer vectors $\{\mbox{\bf x}_1,\ldots,\mbox{\bf x}_m\}\subset [1,N]^m$
; 

				 $\mbox{\rm Flag} :=\mbox{\rm Flag} \land \bigwedge_{i=1}^m(E(\mbox{\bf x}_i)=0)$
; 

				 $\mbox{\rm ntimes}:=\mbox{\rm ntimes}+1$
} ;


		 if $\mbox{\rm Flag}$
then ``Yes'' else ``No'' 

En este caso la probabilidad de error es $\frac{1}{2^t}$.