Definability and fast quantifier elimination in algebraically closed fields
From MaRDI portal
algebraically closed fieldsBezout's theoremconstructible setdefinabilityprenex first order formulasquantifier elimination proceduretime bound
Quantifier elimination, model completeness, and related topics (03C10) Model-theoretic algebra (03C60) Complexity of computation (including implicit computational complexity) (03D15) Connections between field theory and logic (12L99) Applications of logic to commutative algebra (13L05) Elementary questions in algebraic geometry (14A25)
A celebrated theorem of Tarski asserts the existence of a primitively recursive procedure for elimination of quantifiers in algebraically closed fields. The present work - an extended version of papers by \textit{J. Heintz} and \textit{R. Wüthrich} [SIGSAM Bull. 9, No.4, 11 (1975)] and by \textit{J. Heintz} [Fundamentals of computation theory '79, Proc. Conf., Berlin/Wendisch-Rietz 1979, 160-166 (1979; Zbl 0439.03003)] - is devoted to the theorem above and to related definability problems from the point of view of complexity. The main result proved in this paper shows that there exists a quantifier elimination procedure for algebraically closed fields with a time bound which is polynomial in degree and maximum length of the coefficients of the polynomials appearing in the input formula but double exponential in the number of variables of the input formula. A closely related question concerning the cardinality of the finite sets definable by prenex first order formulas in the language of fields is also investigated. The main parameters occurring in the answer to this question are the sum of the degrees of the polynomials, the total number of variables, and the number of bounded variables in the formulas under consideration. The method is based on a version of Bezout's theorem without multiplicities, called by the author the Bezout-inequality.
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
Cites work
- An Extension of Strassen’s Degree Bound
- Constructions in Algebra
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Further Pathologies in Algebraic Geometry
- Generic local structure of the morphisms in commutative algebra
- scientific article; zbMATH DE number 3685447 (Why is no real title available?)
- scientific article; zbMATH DE number 3723860 (Why is no real title available?)
- scientific article; zbMATH DE number 3759547 (Why is no real title available?)
- scientific article; zbMATH DE number 3765129 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3564960 (Why is no real title available?)
- scientific article; zbMATH DE number 3445379 (Why is no real title available?)
- scientific article; zbMATH DE number 3222940 (Why is no real title available?)
- scientific article; zbMATH DE number 3235754 (Why is no real title available?)
- scientific article; zbMATH DE number 3279238 (Why is no real title available?)
- scientific article; zbMATH DE number 3280853 (Why is no real title available?)
- scientific article; zbMATH DE number 3390942 (Why is no real title available?)
- Lower bounds for polynomials with algebraic coefficients
- Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
- Systems of distinct representatives and linear algebra
- The complexity of partial derivatives
Cited in
(only showing first 100 items - show all)- On the complexity of counting components of algebraic varieties
- Irreducibility of multivariate polynomials
- The complexity of linear problems in fields
- A bibliography of quantifier elimination for real closed fields
- Solving systems of polynomial inequalities in subexponential time
- Real quantifier elimination is doubly exponential
- On the order of approximation in approximative triadic decompositions of tensors
- Complexity of computations in Commutative Division of the USSR Academy of Sciences
- Equations for the projective closure and effective Nullstellensatz
- 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
- Counting connected components of a semialgebraic set in subexponential time
- Implicitization of rational parametric equations
- Complexity of deciding Tarski algebra
- On the parallel complexity of the polynomial ideal membership problem
- Topology of generic multijet preimages and blow-up via Newton interpolation
- Trajectories of polynomial vector fields and ascending chains of polynomial ideals
- A sparse effective Nullstellensatz
- An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
- Construction of roadmaps in semi-algebraic sets
- Lower bounds for diophantine approximations
- Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz
- Elimination of constants from machines over algebraically closed fields
- Straight-line programs in geometric elimination theory
- Complexity bounds in elimination theory -- a survey.
- On the number of sets definable by polynomials
- Effective equidimensional decomposition of affine varieties
- Transfer theorems via sign conditions
- A Pommaret bases approach to the degree of a polynomial ideal
- Polynomial bound on the local Betti numbers of a real analytic germ
- Configurations of lines in space and combinatorial rigidity
- Complexity of triangular representations of algebraic sets
- On the bit complexity of polynomial system solving
- The dynamical Mordell-Lang problem for Noetherian spaces
- Polynomial bounds for invariant functions separating orbits
- Lower bounds for arithmetic networks
- Lower bound for the approximative complexity
- Functional programming concepts and straight-line programs in computer algebra
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Complexity results for triangular sets
- Complexity of stratifications of semi-Pfaffian sets
- Bounds of traces in complete intersections and degrees in the Nullstellensatz
- Lower bounds for arithmetic networks. II: Sum of Betti numbers
- On the affine Bezout inequality
- Semi-algebraic decision complexity, the real spectrum, and degree
- The number of reducible space curves over a finite field
- Time-space tradeoffs in algebraic complexity theory
- Deformation techniques for efficient polynomial equation solving.
- The complexity of local dimensions for constructible sets
- Estimates on the number of \(\mathbb{F}_q\)-rational solutions of variants of diagonal equations over finite fields
- Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem
- On Bézout inequalities for non-homogeneous polynomial ideals
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- Bounds on the torsion subgroup schemes of Néron-Severi group schemes
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- On the number of solutions of systems of certain diagonal equations over finite fields
- The dimension growth conjecture, polynomial in the degree and without logarithmic factors
- Elimination for generic sparse polynomial systems
- Distinct distances on curves via rigidity
- Intrinsic complexity estimates in polynomial optimization
- Complexity of solving parametric polynomial systems
- On the geometry of polar varieties
- Complexity of deciding the first-order theory of real closed fields
- Factorization patterns on nonlinear families of univariate polynomials over a finite field
- Degeneracy loci and polynomial equation solving
- On the number of points of algebraic sets over finite fields
- Sparse differential resultant for Laurent differential polynomials
- Multilevel polynomial partitions and simplified range searching
- A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties
- Poisson algebras via model theory and differential-algebraic geometry
- On the efficiency of effective Nullstellensätze
- Generalized polar varieties: geometry and algorithms
- Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
- Improved complexity bounds for counting points on hyperelliptic curves
- On the value set of small families of polynomials over a finite field. I
- On the probability distribution of singular varieties of given corank
- Computing multihomogeneous resultants using straight-line programs
- Change of order for regular chains in positive dimension
- Upper bounds on the distribution of the condition number of singular matrices
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Improved explicit estimates on the number of solutions of equations over a finite field
- On the complexity of the resolvent representation of some prime differential ideals
- Effective differential Nullstellensatz for ordinary DAE systems with constant coefficients
- Quantitative aspects of the generalized differential Lüroth's theorem
- Computing generators of the ideal of a smooth affine algebraic variety
- On the complexity exponent of polynomial system solving
- On the computation of rational solutions of underdetermined systems over a finite field
- Quantifier elimination theory and maps which preserve semipositivity
- On the number of zero-patterns of a sequence of polynomials
- Degree and dimension estimates for invariant ideals of P-solvable recurrences
- Puiseux expansions and nonisolated points in algebraic varieties
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- scientific article; zbMATH DE number 4014674 (Why is no real title available?)
- Counting critical formations on the circle: algebraic-geometric and Morse-theoretic bounds
- Computational aspects of the coordinate ring of an algebraic variety
- Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
- Definable sets in algebraically closed valued fields: elimination of imaginaries
- Fast computation of a rational point of a variety over a finite field
- 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
- Random algebraic construction of extremal graphs
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)
