Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields

DOI10.1016/0022-4049(90)90159-FzbMath0716.03023OpenAlexW2078730239MaRDI QIDQ752692

Jacques Morgenstern, Noaï Fitchas, Andre Galligo

Publication date: 1990

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-4049(90)90159-f

zbMATH Keywords

algorithmsparallelismelementary theory of algebraically closed fieldsfast quantifier elimination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Model theory of fields (12L12) Quantifier elimination, model completeness, and related topics (03C10)

Related Items

Elimination of constants from machines over algebraically closed fields, Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties, On the number of zero-patterns of a sequence of polynomials, On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Elimination for generic sparse polynomial systems, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, A new method to obtain lower bounds for polynomial evaluation, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Back-and-forth systems for generic curves and a decision algorithm for the limit theory, Computing bases of complete intersection rings in Noether position, Solving degenerate sparse polynomial systems faster, Sur la complexité du principe de Tarski-Seidenberg, Complexity bounds in elimination theory -- a survey., On the number of sets definable by polynomials, VPSPACE and a transfer theorem over the complex field, Elimination of parameters in the polynomial hierarchy, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Transfer theorems via sign conditions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Fields of large transcendence degree generated by values of elliptic functions
• Bounds for the degrees in the Nullstellensatz
• The complexity of linear problems in fields
• On the complexity of computing syzygies
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
• THE COMPLEXITY OF THE DECISION PROBLEM FOR THE FIRST ORDER THEORY OF ALGEBRAICALLY CLOSED FIELDS
• Algèbre linéaire sur $K[X_1,\dots,X_n$ et élimination]
• Constructions in Algebra
• Sharp Effective Nullstellensatz