On the intrinsic complexity of elimination problems in effective Algebraic Geometry
Preprint
Abstract
The representation of polynomials by arithmetic circuits evaluating them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Software Engineering and complexity in effective Algebraic GeometryJournal of Complexity, 2012
- Lower complexity bounds for interpolation algorithmsJournal of Complexity, 2011
- On the Time-Space Complexity of Geometric Elimination ProceduresApplicable Algebra in Engineering, Communication and Computing, 2001
- Straight-line programs in geometric elimination theoryJournal of Pure and Applied Algebra, 1998
- On the intractability of Hilbert’s Nullstellensatz and an algebraic version of “NP≠P?”Duke Mathematical Journal, 1995
- On the Intrinsic Complexity of Elimination TheoryJournal of Complexity, 1993
- The membership problem for unmixed polynomial ideals is solvable in single exponential timeDiscrete Applied Mathematics, 1991
- Greatest common divisors of polynomials given by straight-line programsJournal of the ACM, 1988
- On the Number of Nonscalar Multiplications Necessary to Evaluate PolynomialsSIAM Journal on Computing, 1973
- Generic Local Structure of the Morphisms in Commutative AlgebraLecture Notes in Mathematics, 1973