next up previous contents
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{displaymath}\begin{array}{rlcrl}
1. & c\in Z &\Rightarrow & c\in \mbox{\...
...al (F G) = \partial (F) + \partial (G) \end{array}
\end{array}\end{displaymath}

Sea

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

Consideremos el problema siguiente:


Instancia:
\begin{pagi}{34}$E\in\mbox{\it EPE}(\mbox{\bf X})$\end{pagi}
Solución:
\begin{pagi}{34}$\left\{\begin{array}{ll}1 &\mbox{\rm si } E\in \mbox{\rm Cero} \\ 0 &\mbox{\rm si } E\not\in \mbox{\rm Cero}\end{array}\right.$\end{pagi}



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-1Nm raices enteras en el rectángulo [1,N]m.

 

Guillermo Morales-Luna
2000-07-10