Data structures and polynomial equation solving

DAVID CASTRO,; MARC GIUSTI,; JOOS HEINTZ; GUILLERMO MATERA; LUIS MIGUEL PARDO

Buenos Aires

Conferencia; Jornadas Argentinas de Informática e Investigación Operativa; 2001

Sociedad Argentina de Informática e Investigación Operativa

Elimination theory is at the origin of algebraic geometry in the 19-th century and deals with algorithmic solving of multivariate polynomial systems over the complex numbers, or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity if universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e. polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let be given a data structure and together with data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids "unnecessary" branchings and that P admits the efficient computation of certain natural limit objects (as e.g. the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P cannot be a polynomial time algorithm. The paper contains different variants of this result which are formulated and discussed both from the point of view of exact (i.e. symbolic) as well as from the point of view of approximative (i.e. numeric) computing.