The hardness of polynomial equation solving

From MaRDI portal



Abstract: 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.


The authors prove that the nonpolynomial complexity character of the symbolic geometric elimination procedures is a consequence of the information encoded by the particular data structures. The main result is the following. Let be given an arbitrary continuous data structure encoding input and output objects of elimination theory and a universal elimination algorithm solving arbritrary parametric polynomial equation systems. Supposing that the algorithm avoids unnecessary branchings and admits the efficient computation of certain natural limit objects, then the algorithm cannot be a polynomial time one.




Cited in
(36)


Describes a project that uses

Uses Software






This page was built for publication: The hardness of polynomial equation solving

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1430505)