The intrinsic complexity of parametric elimination methods

zbMATH Open0915.68073arXivalg-geom/9707006MaRDI QIDQ4233451FDOQ4233451

Joos Heintz, Guillermo Matera, Luis Miguel Pardo, Rosita Wachenchauzer

Publication date: 18 March 1999

Abstract: This paper is devoted to the complexity analysis of a particular property, called "algebraic robustness" owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must neccessarily have an exponential sequential time complexity.

Full work available at URL: https://arxiv.org/abs/alg-geom/9707006

Recommendations

• Kronecker's smart, little black boxes
• The hardness of polynomial equation solving
• On the intrinsic complexity of elimination problems in effective algebraic geometry
• On the time-space complexity of geometric elimination procedures

zbMATH Keywords

polynomial system solvinggeometric robustnesselimination complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (10)

• A concise proof of the Kronecker polynomial system solver from scratch
• Systems of rational polynomial equations have polynomial size approximate zeros on the average
• Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
• Some lower bounds for the complexity of the linear programming feasibility problem over the reals
• On the time-space complexity of geometric elimination procedures
• The hardness of polynomial equation solving
• Fast computation of a rational point of a variety over a finite field
• On the intrinsic complexity of elimination theory
• Kronecker's smart, little black boxes
• Deformation techniques to solve generalised Pham systems

This page was built for publication: The intrinsic complexity of parametric elimination methods

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