Definability and fast quantifier elimination in algebraically closed fields
From MaRDI portal
definabilityconstructible setBezout's theoremalgebraically closed fieldsprenex first order formulasquantifier elimination proceduretime bound
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)
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
- 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?)
- 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
- 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)- Semi-algebraic decision complexity, the real spectrum, and degree
- Equations for the projective closure and effective Nullstellensatz
- Elimination for generic sparse polynomial systems
- Complexity of deciding the first-order theory of real closed fields
- On the parallel complexity of the polynomial ideal membership problem
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Computational aspects of the coordinate ring of an algebraic variety
- Computing generators of the ideal of a smooth affine algebraic variety
- Upper bounds on the distribution of the condition number of singular matrices
- Ascending chains of ideals in the polynomial ring
- Quantifier elimination in separably closed fields of finite imperfectness degree
- 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
- Shifted varieties and discrete neighborhoods around varieties
- Topology of generic multijet preimages and blow-up via Newton interpolation
- Puiseux expansions and nonisolated points in algebraic varieties
- On k-constructable sets, k-elementary formulae, and elimination theory.
- Trajectories of polynomial vector fields and ascending chains of polynomial ideals
- On the order of approximation in approximative triadic decompositions of tensors
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Elimination of constants from machines over algebraically closed fields
- Distinct distances on curves via rigidity
- scientific article; zbMATH DE number 4014674 (Why is no real title available?)
- Complexity bounds in elimination theory -- a survey.
- On the computation of rational solutions of underdetermined systems over a finite field
- WELL-FORMED SET REPRESENTATIONS OF SOLIDS
- Computation of differential Chow forms for ordinary prime differential ideals
- Degree and dimension estimates for invariant ideals of \(P\)-solvable recurrences
- On the number of solutions of systems of certain diagonal equations over finite fields
- Solving systems of polynomial inequalities over a real closed field in subexponential time
- Poisson algebras via model theory and differential-algebraic geometry
- How to compute the Chow form of an unmixed polynomial ideal in single exponential time
- Algebraic dimension over Frobenius fields
- On the number of sets definable by polynomials
- Polynomial bounds for invariant functions separating orbits
- Complexity of computations in Commutative Division of the USSR Academy of Sciences
- Random algebraic construction of extremal graphs
- Finding connected components of a semialgebraic set in subexponential time
- Fast computation of a rational point of a variety over a finite field
- A bibliography of quantifier elimination for real closed fields
- Transfer theorems via sign conditions
- 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
- Practically solving some problems expressed in the first order theory of real closed field
- Elimination of unknowns for systems of algebraic differential-difference equations
- Complexity of triangular representations of algebraic sets
- On the complexity of computing a random Boolean function over the reals
- Intrinsic complexity estimates in polynomial optimization
- Back-and-forth systems for generic curves and a decision algorithm for the limit theory
- Sparse differential resultant for Laurent differential polynomials
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Complexity of stratifications of semi-Pfaffian sets
- On the number of points of algebraic sets over finite fields
- A Pommaret bases approach to the degree of a polynomial ideal
- Complexity of deciding Tarski algebra
- Counting connected components of a semialgebraic set in subexponential time
- Implicitization of rational parametric equations
- Polar varieties, Bertini's theorems and number of points of singular complete intersections over a finite field
- Explicit estimates for the number of rational points of singular complete intersections over a finite field
- Deformation techniques to solve generalised Pham systems
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Improved explicit estimates on the number of solutions of equations over a finite field
- Sur la complexité du principe de Tarski-Seidenberg
- Quantitative aspects of the generalized differential Lüroth's theorem
- Solving systems of polynomial inequalities in subexponential time
- Effective differential Lüroth's theorem
- Change of order for regular chains in positive dimension
- The complexity of local dimensions for constructible sets
- Computing multihomogeneous resultants using straight-line programs
- A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties
- A sparse effective Nullstellensatz
- Kronecker's and Newton's approaches to solving: a first comparison
- Distinct Distances on Algebraic Curves in the Plane
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- Functional programming concepts and straight-line programs in computer algebra
- Algorithms yield upper bounds in differential algebra
- Lower bound for the approximative complexity
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- Generalized polar varieties: geometry and algorithms
- Lower bounds for arithmetic networks. II: Sum of Betti numbers
- On the complexity of the resolvent representation of some prime differential ideals
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Effective uniform bounding in partial differential fields
- Complexity results for triangular sets
- Irreducibility of multivariate polynomials
- Generalized polar varieties and an efficient real elimination.
- Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
- On the complexity of counting components of algebraic varieties
- On the affine Bezout inequality
- Deciding consistency of systems of exponential-polynomial inequalities in subexponential time
- Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz
- Variety evasive sets
- Probabilistic algorithms for computing resolvent representations of regular differential ideals
- Straight-line programs in geometric elimination theory
- 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
- Bounds of traces in complete intersections and degrees in the Nullstellensatz
- An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
- Effective definability of Kolchin polynomials
- Construction of roadmaps in semi-algebraic sets
- Counting critical formations on the circle: algebraic-geometric and Morse-theoretic bounds
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)
