HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On the intrinsic complexity of elimination theory

Abstract : We consider the intrinsic complexity of selected algorithmic problems of classical elimination theory in algebraic geometry. The inputs and outputs of these problems are given by finite sets of polynomials which we represent alternatively in dense forme or by straight line programs. We begin with an overview on the known upper bounds for the sequential and parallel time complexity of these problems and show then that in the most important cases these bounds are tight. Our lower bound results include both the relative and the absolute viewpoint of complexity theory. On one side we give reductions of fundamental questions of elimination theory to NP- and P#- complete problems and on the other side we show that some of these questions may have exponential size outputs. In this way we confirm the intrinsically exponential character of algorithmic problems in elimination theory whatever the type of data structure may be.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:13:57 PM
Last modification on : Friday, February 4, 2022 - 3:18:39 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 6:58:36 PM


  • HAL Id : inria-00074751, version 1



Joos Heintz, Jacques Morgenstern. On the intrinsic complexity of elimination theory. [Research Report] RR-1923, INRIA. 1993. ⟨inria-00074751⟩



Record views


Files downloads