The hardness of polynomial equation solving
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.
- Deformation techniques for sparse systems
- On the bit complexity of polynomial system solving
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Fast computation of discrete invariants associated to a differential rational mapping
- Software engineering and complexity in effective algebraic geometry
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- On the geometry of polar varieties
- Generalized polar varieties: geometry and algorithms
- Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
- A concise proof of the Kronecker polynomial system solver from scratch
- Lower complexity bounds for interpolation algorithms
- An arithmetic Poisson formula for the multi-variate resultant
- Quiz games as a model for information hiding
- Kronecker's smart, little black boxes
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant
- Fast computation of a rational point of a variety over a finite field
- scientific article; zbMATH DE number 5124810 (Why is no real title available?)
- The intrinsic complexity of parametric elimination methods
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- Le rôle des structures de données dans les problèmes d'élimination
- Generalized polar varieties and an efficient real elimination.
- On the intrinsic complexity of elimination problems in effective algebraic geometry
- On the time-space complexity of geometric elimination procedures
- Polynomial equation solving by lifting procedures for ramified fibers
- Deformation techniques to solve generalised Pham systems
- Fast linear homotopy to find approximate zeros of polynomial systems
- Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
- On the complexity of Chow and Hurwitz forms
- Deciding polynomial-transcendental problems
- Dedicated to the memory of Joos Heintz
- On the geometric degree of the tangent bundle of a smooth algebraic variety
- On the solution of the polynomial systems arising in the discretization of certain ODEs
- Approximation of the solution of certain nonlinear ODEs with linear complexity
- On the intrinsic complexity of point finding in real singular hypersurfaces
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
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)