Siguiente: . Un nivel arriba: Algoritmos probabilísticos Anterior: Algoritmos probabilísticos

Expresiones polinomiales nulas

Sea $\mbox{\bf X}=\{X_1,\ldots,X_m\}$ un conjunto de m variables. Definimos la clase de expresiones polinomiales enteras $\mbox{\it EPE}(\mbox{\bf X})$, y el grado de cada uno de sus elementos, de manera inductiva como sigue:

$$\begin{array}{rlcrl} 1. & c\in Z &\Rightarrow & c\in \mbox{\... ...al (F G) = \partial (F) + \partial (G) \end{array} \end{array}$$

Sea

$$\mbox{\rm Cero}=\{E\in\mbox{\it EPE}(\mbox{\bf X})\vert E\equiv 0\}.$$

Consideremos el problema siguiente:


Instancia:

Solución:




Observaciones: 1. Desarrollando el polinomio dado como una suma de monomios, ordenados lexicográficamente, se resuelve el problema en tiempo exponencial. 2. Si $F(X_1,\ldots,X_m)\not\in \mbox{\rm Cero}$ y $N\geq c\cdot \partial(F)$ entonces F posee a lo sumo c^-1N^m raices enteras en el rectángulo [1,N]^m.