2003/01/18 by David Castro, David J. Castro, Castro, David +9
Computer Science · Mathematics · #14Q15 #68Q25 #68W30 #Algebraic Geometry (math.AG) #Applied mathematics #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #FOS: Mathematics #Mathematical analysis #Mathematics #Matrix polynomial #Numerical Methods and Algorithms #Polynomial #Polynomial and algebraic computation #math.AC #math.AG #msc:14Q15 #msc:68Q25 #msc:68W30
paper · pdf · doi:10.48550/arxiv.math/0301194
82 pages, submitted to Foundations of Computational Mathematics
arxiv created 2003/01/18 · openalex publication_date 2003/01/18 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper we investigate the intrinsic sequential time complexity of 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 such a data structure and together with this 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 and discusses their practical implications.