On the intrinsic complexity of elimination theory

DOI10.1006/JCOM.1993.1031zbMath0835.68054OpenAlexW2064751579MaRDI QIDQ1330148

Jacques Morgenstern, Joos Heintz

Publication date: 17 August 1994

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00074751/file/RR-1923.pdf

zbMATH Keywords

elimination theorystraight-line programsparallel time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items (17)

Black-box polynomial resultants ⋮ On Kolmogorov complexity in the real Turing machine setting ⋮ Lower bounds for diophantine approximations ⋮ Simplified lower bounds for polynomials with algebraic coefficients ⋮ On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)? ⋮ Straight-line programs in geometric elimination theory ⋮ Gröbner bases for polynomial systems with parameters ⋮ Continuity properties for flat families of polynomials. I: Continuous parametrizations ⋮ Model checking in the modal \(\mu \)-calculus and generic solutions ⋮ Lower complexity bounds for interpolation algorithms ⋮ An arithmetic Poisson formula for the multi-variate resultant ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Counting and Gröbner bases ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ A new method to obtain lower bounds for polynomial evaluation ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ Complexity bounds in elimination theory -- a survey.

This page was built for publication: On the intrinsic complexity of elimination theory