The intrinsic complexity of parametric elimination methods

J. Heintz(1,2) G. Matera(2,3) L. M. Pardo(1) R. Wachenchauzer(4)

  1. Depto. de Matemáticas, Est. y Comp., Facultad de Ciencias, Univesidad de Cantabria, E-39071 SANTANDER, Spain. heintz@matsun1.matesco.unican.es
  2. Depto. de Matemáticas, FCEyN, Universidad de Buenos Aires, Ciudad Universitaria, Pab. I, (1428) BUENOS AIRES, Argentina. gmatera@dm.uba.ar
  3. Instituto de Ciencias, Universidad Nacional de Gral. Sarmiento, Roca 850, (1663) San Miguel - Pcia. de Buenos Aires, Argentina.
  4. Departamento de Computación, FCEyN, Universidad de Buenos Aires, Ciudad Universitaria, Pab. I, (1428) BUENOS AIRES, Argentina. rosita@dc.uba.ar

Abstract:

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.

Keywords.Polynomial system solving, 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.