The intrinsic complexity of parametric elimination methods
From MaRDI portal
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.
Recommendations
Cited in
(12)- On the intrinsic complexity of elimination theory
- The hardness of polynomial equation solving
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Software engineering and complexity in effective algebraic geometry
- Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
- A concise proof of the Kronecker polynomial system solver from scratch
- Kronecker's smart, little black boxes
- Fast computation of a rational point of a variety over a finite field
- On the time-space complexity of geometric elimination procedures
- Deformation techniques to solve generalised Pham systems
- Dedicated to the memory of Joos Heintz
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
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)
