The hardness of polynomial equation solving

Simple item page
dc.creatorCastro, David
dc.creatorGiusti, Marc
dc.creatorHeintz, Joos
dc.creatorMatera, Guillermo
dc.creatorPardo, Luis Miguel
dc.date2003-01-18
dc.date.accessioned2026-07-07T04:54:31Z
dc.date.available2026-07-07T04:54:31Z
dc.descriptionIn 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.
dc.description82 pages, submitted to Foundations of Computational Mathematics
dc.identifierhttps://arxiv.org/abs/math/0301194
dc.identifierhttp://arxiv.org/abs/math/0301194
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/66284
dc.subjectCommutative Algebra
dc.subjectAlgebraic Geometry
dc.subject14Q15; 68Q25; 68W30
dc.titleThe hardness of polynomial equation solving
dc.typetext

Files

Collections

arXiv