Complexity bounds in elimination theory -- a survey.

DOI10.1016/S0378-4754(96)00017-1zbMath1037.14504MaRDI QIDQ1565824

Pablo Solernó

Publication date: 27 May 2003

Published in: Mathematics and Computers in Simulation (Search for Journal in Brave)

zbMATH Keywords

complexity; elimination theory; computer algebra; algebraic variety; straight line program

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

14Q99: Computational aspects in algebraic geometry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Degree bounds for the division problem in polynomial ideals
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• Bounds for the degrees in the division problem
• Bounds for the degrees in the Nullstellensatz
• Résolution des systèmes d'équations algébriques
• Le formalisme du résultant. (The formalism of resultant)
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• On the intrinsic complexity of elimination theory
• On the representation of rational functions of bounded complexity
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• On the efficiency of effective Nullstellensätze
• Berechnung und Programm. I
• Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
• Greatest common divisors of polynomials given by straight-line programs
• Sharp Effective Nullstellensatz