Definability and fast quantifier elimination in algebraically closed fields
From MaRDI portal
Publication:798314
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
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)
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
- 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
- Puiseux expansions and nonisolated points in algebraic varieties
- 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
- 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
- On k-constructable sets, k-elementary formulae, and elimination theory.
- Complexity of computations in Commutative Division of the USSR Academy of Sciences
- Back-and-forth systems for generic curves and a decision algorithm for the limit theory
- 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
- 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
- Degree and dimension estimates for invariant ideals of \(P\)-solvable recurrences
- 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
- On the complexity of computing a random Boolean function over the reals
- Multilevel polynomial partitions and simplified range searching
- Degeneracy loci and polynomial equation solving
- Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics
- Irredundant bases for finite groups of Lie type
- Estimates on the number of \(\mathbb{F}_q\)-rational solutions of variants of diagonal equations over finite fields
- The dimension growth conjecture, polynomial in the degree and without logarithmic factors
- Definable equivalence relations on algebraically closed fields
- Factorization patterns on nonlinear families of univariate polynomials over a finite field
- Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem
- On maps which preserve semipositivity and quantifier elimination theory for real numbers
- Improved complexity bounds for counting points on hyperelliptic curves
- Partial differential Chow forms and a type of partial differential Chow varieties
- Variety evasive subspace families
- Differential Elimination for Dynamical Models via Projections with Applications to Structural Identifiability
- On Bézout inequalities for non-homogeneous polynomial ideals
- Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results
- On multiplicative energy of subsets of varieties
- Degree bound for toric envelope of a linear algebraic group
- A single exponential time algorithm for homogeneous regular sequence tests
- Interpolation by decomposable univariate polynomials
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- Surjective morphisms from affine space to its Zariski open subsets
- An approach to the moments subset sum problem through systems of diagonal equations over finite fields
- Free-Form Modeling in Bilateral Brep and CSG Representation Schemes
- Spectral equivalence of smooth group schemes over principal ideal local rings
- The number of reducible space curves over a finite field
- Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
- Bounds on the torsion subgroup schemes of Néron-Severi group schemes
- Fast Algorithms for Discrete Differential Equations
- Quantifier elimination theory and maps which preserve semipositivity
- Computing bases of complete intersection rings in Noether position
- Partition and analytic rank are equivalent over large fields
- Bounds on the torsion subgroups of Néron-Severi groups
- Spectral norm of a symmetric tensor and its computation
- Time-space tradeoffs in algebraic complexity theory
- Effective de Rham cohomology — The general case
- 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
- 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
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)
