The hardness of polynomial equation solving

DOI10.1007/S10208-002-0065-7zbMath1049.68070arXivmath/0301194OpenAlexW2088922099MaRDI QIDQ1430505

D. Massart

Publication date: 27 May 2004

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0301194

zbMATH Keywords

complexitypolynomial equationseliminationcontinuous encodingdata stuctures

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (26)

Quiz games as a model for information hiding ⋮ Fast computation of discrete invariants associated to a differential rational mapping ⋮ On the solution of the polynomial systems arising in the discretization of certain ODEs ⋮ On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant ⋮ Approximation of the solution of certain nonlinear ODEs with linear complexity ⋮ Generalized polar varieties: geometry and algorithms ⋮ Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study ⋮ 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 ⋮ A concise proof of the Kronecker polynomial system solver from scratch ⋮ Lower complexity bounds for interpolation algorithms ⋮ Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces ⋮ An arithmetic Poisson formula for the multi-variate resultant ⋮ Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers ⋮ On the bit complexity of polynomial system solving ⋮ On the geometry of polar varieties ⋮ On the intrinsic complexity of point finding in real singular hypersurfaces ⋮ On the complexity of Chow and Hurwitz forms ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density ⋮ Deformation techniques for sparse systems ⋮ Unnamed Item ⋮ Fast computation of a rational point of a variety over a finite field ⋮ Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity ⋮ Systems of rational polynomial equations have polynomial size approximate zeros on the average

Uses Software

• Unnamed Item

This page was built for publication: The hardness of polynomial equation solving