The hardness of polynomial equation solving

Details The hardness of polynomial equation solving The hardness of polynomial equation solving

2003-01-18

arxiv.org/abs/math/0301194v1

Mathematics

Commutative Algebra

82 pages, submitted to Foundations of Computational Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The hardness of polynomial equation solving does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The hardness of polynomial equation solving, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The hardness of polynomial equation solving will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-646570