The hardness of polynomial equation solving (Q1430505)

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.