Definability and fast quantifier elimination in algebraically closed fields

DOI10.1016/0304-3975(83)90002-6zbMATH Open0546.03017OpenAlexW2035153735MaRDI QIDQ798314FDOQ798314

Authors: Joos Heintz 

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90002-6

Recommendations

• scientific article; zbMATH DE number 3895043
• scientific article; zbMATH DE number 4014674
• On the combinatorial and algebraic complexity of quantifier elimination
• On the number of sets definable by polynomials
• scientific article; zbMATH DE number 871442
• Real quantifier elimination is doubly exponential
• Computer Science Logic
• An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
• Quantifier elimination in separably closed fields of finite imperfectness degree

zbMATH Keywords

definabilityconstructible setBezout's theoremalgebraically closed fieldsprenex first order formulasquantifier elimination proceduretime bound

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Complexity of computation (including implicit computational complexity) (03D15) Quantifier elimination, model completeness, and related topics (03C10) Elementary questions in algebraic geometry (14A25) Applications of logic to commutative algebra (13L05) Connections between field theory and logic (12L99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of partial derivatives
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Generic local structure of the morphisms in commutative algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• Title not available (Why is that?)
• Lower bounds for polynomials with algebraic coefficients
• Title not available (Why is that?)
• Constructions in Algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Systems of distinct representatives and linear algebra
• Title not available (Why is that?)
• Further Pathologies in Algebraic Geometry
• Title not available (Why is that?)
• An Extension of Strassen’s Degree Bound
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Shifted varieties and discrete neighborhoods around varieties
• Degree and Dimension Estimates for Invariant Ideals of $$P$$ -Solvable Recurrences
• On the order of approximation in approximative triadic decompositions of tensors
• Systems of rational polynomial equations have polynomial size approximate zeros on the average
• Random algebraic construction of extremal graphs
• Transfer theorems via sign conditions
• Algebraic dimension over Frobenius fields
• Computational aspects of the coordinate ring of an algebraic variety
• A bibliography of quantifier elimination for real closed fields
• Bit complexity for computing one point in each connected component of a smooth real algebraic set
• On the parallel complexity of the polynomial ideal membership problem
• WELL-FORMED SET REPRESENTATIONS OF SOLIDS
• Poisson algebras via model theory and differential-algebraic geometry
• Complexity of triangular representations of algebraic sets
• Computing generators of the ideal of a smooth affine algebraic variety
• Elimination of constants from machines over algebraically closed fields
• On the computation of rational solutions of underdetermined systems over a finite field
• Polynomial bounds for invariant functions separating orbits
• Finding connected components of a semialgebraic set in subexponential time
• Distinct distances on curves via rigidity
• Topology of generic multijet preimages and blow-up via Newton interpolation
• Trajectories of polynomial vector fields and ascending chains of polynomial ideals
• Puiseux Expansions and Nonisolated Points in Algebraic Varieties
• Fast computation of a rational point of a variety over a finite field
• Quantifier elimination in separably closed fields of finite imperfectness degree
• On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case
• Semi-algebraic decision complexity, the real spectrum, and degree
• Computation of differential Chow forms for ordinary prime differential ideals
• Title not available (Why is that?)
• On k-constructable sets, k-elementary formulae, and elimination theory.
• Complexity of computations in Commutative Division of the USSR Academy of Sciences
• Complexity of stratifications of semi-Pfaffian sets
• Elimination for generic sparse polynomial systems
• Upper bounds on the distribution of the condition number of singular matrices
• Title not available (Why is that?)
• Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
• Sparse difference resultant
• Polynomial bound on the local Betti numbers of a real analytic germ
• Configurations of lines in space and combinatorial rigidity
• Effective difference elimination and nullstellensatz
• Elimination of unknowns for systems of algebraic differential-difference equations
• Ascending chains of ideals in the polynomial ring
• Practically solving some problems expressed in the first order theory of real closed field
• Complexity bounds in elimination theory -- a survey.
• Solving systems of polynomial inequalities over a real closed field in subexponential time
• How to compute the Chow form of an unmixed polynomial ideal in single exponential time
• Intrinsic complexity estimates in polynomial optimization
• Sparse differential resultant for Laurent differential polynomials
• Complexity of deciding the first-order theory of real closed fields
• Equations for the projective closure and effective Nullstellensatz
• On the number of solutions of systems of certain diagonal equations over finite fields
• On the number of sets definable by polynomials
• Effective uniform bounding in partial differential fields
• A parametric representation of totally mixed Nash equilibria
• Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
• Computing multihomogeneous resultants using straight-line programs
• Deciding consistency of systems of exponential-polynomial inequalities in subexponential time
• On the value set of small families of polynomials over a finite field. I
• Change of order for regular chains in positive dimension
• Variety evasive sets
• Title not available (Why is that?)
• On the bit complexity of polynomial system solving
• Evaluating geometric queries using few arithmetic operations
• Complexity results for triangular sets
• On the number of zero-patterns of a sequence of polynomials
• Effective differential Nullstellensatz for ordinary DAE systems with constant coefficients
• A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties
• Algorithms yield upper bounds in differential algebra
• Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
• Complexity of factoring and calculating the GCD of linear ordinary differential operators
• Title not available (Why is that?)
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Bit-size estimates for triangular sets in positive dimension
• Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
• A Gröbner free alternative for polynomial system solving
• Lower bounds for diophantine approximations
• Quantitative aspects of the generalized differential Lüroth's theorem
• Sur la complexité du principe de Tarski-Seidenberg
• Effective differential Lüroth's theorem
• Properness defects of projection and minimal discriminant variety
• A linear algebra approach to the differentiation index of generic DAE systems
• 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
• On the complexity exponent of polynomial system solving
• Complexity of deciding Tarski algebra
• Probabilistic algorithms for computing resolvent representations of regular differential ideals
• Straight-line programs in geometric elimination theory
• Counting critical formations on the circle: algebraic-geometric and Morse-theoretic bounds
• Polynomial equation solving by lifting procedures for ramified fibers
• On the geometry of polar varieties
• Kronecker's and Newton's approaches to solving: a first comparison
• Deformation techniques for efficient polynomial equation solving.
• The complexity of local dimensions for constructible sets
• Distinct Distances on Algebraic Curves in the Plane
• Lower bound for the approximative complexity
• An incidence theorem in higher dimensions
• On computing absolutely irreducible components of algebraic varieties with parameters
• Improved explicit estimates on the number of solutions of equations over a finite field
• Complexity of solving parametric polynomial systems
• On the efficiency of effective Nullstellensätze
• On the complexity of the resolvent representation of some prime differential ideals

This page was built for publication: Definability and fast quantifier elimination in algebraically closed fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q798314)