La búsqueda de algoritmos eficientes
para la resolución de ecuaciones polinomiales,
al menos desde un punto de vista teórico,
conoció un especial desarrollo en los últimos
años, gracias a los sucesivos trabajos de
Grigoriev, Vorobjov, Chistov [7, 15],
Canny [6], Renegar [28]
y de nuestro propio grupo, entre otros,
lográndose exhibir una larga lista de
problemas que pueden ser resueltos en
tiempo simplemente exponencial y espacio
(memoria) polinomial. Tal como se evidencia
en [17], es altamente improbable una
mejora sustancial en este comportamiento.
Sin duda una de las razones más relevantes
de esta imposibilidad (o al menos de la
imposibilidad de obtener algoritmos
eficientes en la práctica) es la
representación de los datos
(en nuestro caso polinomios en varias variables);
resulta evidente que la codificación de estos
datos en su ``forma densa" (como vector de coeficientes),
si bien natural desde el punto de vista matemático,
conduce a una imposibililidad práctica
inobjetable.
Es por ello que a nuestro juicio, solo un cambio en
la codificación podía permitir mejoras sustanciales.
Teniendo en cuenta que las estructuras ``magras" (polinomios que involucren
``pocos" monomios) siempre se revelaron muy inestables en teoría de
eliminación, se consideró la posibilidad de tratar los polinomios por
medio de ``straight-line programs", donde cada polinomio se representa por
medio de un programa que lo evalúa (en particular las entradas de un
algoritmo en este modelo son también algoritmos). Obviamente, para obtener
resultados relevantes con esta codificación eran necesarios nuevos
procedimientos, mejor adaptados. En este sentido, la introducción de la
teoría de dualidad juega un rol central, así también como la
existencia de herramientas informáticas adecuadas (p.ej. [18]).
Se comenzó con estructuras de datos mixtas,
es decir, polinomios de entrada dados en forma densa,
mientras que
los resultados se codifican por medio de programas
de evaluación. Tal es el caso de [10],
[11], [9] y [27] en donde se demuestra la existencia
de algoritmos polinomiales en el tamaño de la entrada (en este caso
necesariamente exponencial en el número de variables, a causa de la
codificación densa). En estos trabajos se tratan respectivamente, el
cálculo de la dimensión de una variedad algebraica, el cálculo de los
polinomios que intervienen en el Teorema de ceros de Hilbert (consistencia
de un sistema de ecuaciones) y la eliminación de cuantificadores sobre
cuerpos algebraicamente cerrados.
En el caso en que los datos de entrada también estén dados con
programas de evaluación, agregando ideas cercanas al método de Newton (a
fin de simplificar los straight-line programs que aparecen) se ha
avanzado hasta la obtención de algoritmos polinomiales en tiempo y espacio
que resuelven sistemas de dimensión cero (ver [12, 14]), siendo los
parámetros involucrados: la longitud del programa que evalúa los datos,
el número de variables, el máximo de los grados de los polinomios del
input y el grado del sistema 
definido como se mencionó más
arriba.
También para el caso de los números reales, se ha obtenido un algoritmo
polinomial en tiempo y espacio, similar a los anteriores, que encuentra
puntos en las componentes conexas de una hipersuperficie regular compacta
(ver [3]). Este es el primer resultado en ese sentido sobre 
.
Otro hecho poco considerado hasta el momento desde el punto de vista
teórico en el estudio de la complejidad de los algoritmos de eliminación
era el referido a la complejidad ``bit", es decir no solo el control
de la cantidad de operaciones en los anillos de base, sino también con
estimación adecuada del costo real que estas operaciones producen. Este
aspecto es tratado en [13].
Para finalizar estas consideraciones sobre algoritmos polinomiales de
eliminación, unas pocas palabras acerca de la implantación. Creemos que
las cotas de complejidad obtenidas, a pesar de que en los casos ``peores"
sigue resultando idéntica a la de los algoritmos conocidos (allí\
coincide con 
y nuestros algoritmos polinomiales en
devienen exponenciales en n), en muchos otros casos pueden dar lugar a
algoritmos prácticos efectivos, como lo demuestran varios ejemplos
realizados en este último tiempo (ver [32]). A tal efecto, en un
trabajo conjunto entre investigadores de las Universidades de Buenos Aires,
San Luis, Cantabria (España), Alcalá (España) y la Escuela
Politécnica (Palaiseau, Francia) reunido bajo la sigla TERA, se están
llevando a cabo las tareas de preparación de una biblioteca de programas
que permita el ataque de problemas concretos de eliminación
algebro-diferencial. (ver el informe [19]). En esta dirección
también pueden mencionarse los algoritmos desarrollados en [25] y la
implementación presentada en [16], donde se trata con algoritmos que
funcionen con un consumo escaso de memoria.
Entre otras tareas afines realizadas dentro del grupo se deben mencionar
también el estudio del cálculo del radical de ideales polinomiales: en
este sentido se obtuvieron algoritmos simplemente exponenciales
bien paralelizables que calculan radicales de ideales geométricamente
Cohen-Macaulay dados por sucesiones regulares (ver [2]). Se trata de
la primer familia de ideales de dimensiones arbitrarias para las que se que
tienen algoritmos subexponenciales (hasta ahora solo era conocido el
resultado para dimensión no mayor a 1).
Finalmente mencionaremos otra aplicación del modelo mediante cálculos de evaluación, esta vez en el campo de la integración formal (ver [24]).