The intrinsic complexity of parametric elimination methods

J. Heintz; G. Matera; L.M. Pardo; R. Wachenchauzer

J. Heintz Depto. de Matemáticas, Est. y Comp., Facultad de Ciencias, Univesidad de Cantabria,
G. Matera Depto. de Matemáticas, FCEyN, Universidad de Buenos Aires - Instituto de Ciencias, Universidad Nacional de Gral. Sarmiento
L.M. Pardo Depto. de Matemáticas, Est. y Comp., Facultad de Ciencias, Univesidad de Cantabria
R. Wachenchauzer Departamento de Computación, FCEyN, Universidad de Buenos Aires

Resumen

This paper is devoted to the complexity analysis of a particular property, called geometric robustness owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must necessarily have an exponential sequential time complexity even if highly performant data structures (as e.g. the straight--line program encoding of polynomials) are used. The paper finishes with the motivated introduction of a new non-uniform complexity measure for zero-dimensional polynomial equation systems, called elimination complexity.

Research was partially supported by the following Argentinian and Spanish grants:UBA-CYT.EX.001, PIP CONICET 4571, DGICYT PB96--0671--C02--02.