Definability and fast quantifier elimination in algebraically closed fields

From MaRDI portal

Publication:798314

Jump to:navigation, search

DOI10.1016/0304-3975(83)90002-6zbMath0546.03017OpenAlexW2035153735MaRDI QIDQ798314

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

zbMATH Keywords

definability constructible set Bezout's theorem algebraically closed fields prenex first order formulas quantifier elimination procedure time bound

Mathematics Subject Classification ID

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) Quantifier elimination, model completeness, and related topics (03C10) Elementary questions in algebraic geometry (14A25)

Related Items

Algorithms yield upper bounds in differential algebra, On multiplicative energy of subsets of varieties, Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field, Practically solving some problems expressed in the first order theory of real closed field, Quantitative aspects of the generalized differential Lüroth's theorem, Random algebraic construction of extremal graphs, On maps which preserve semipositivity and quantifier elimination theory for real numbers, Computing generators of the ideal of a smooth affine algebraic variety, Degree bound for toric envelope of a linear algebraic group, Computational aspects of the coordinate ring of an algebraic variety, On the complexity exponent of polynomial system solving, Ascending chains of ideals in the polynomial ring, Differential Elimination for Dynamical Models via Projections with Applications to Structural Identifiability, Irredundant bases for finite groups of Lie type, Fast Algorithms for Discrete Differential Equations, Surjective morphisms from affine space to its Zariski open subsets, Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics, On the computation of rational solutions of underdetermined systems over a finite field, Quantifier elimination theory and maps which preserve semipositivity, Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results, Partition and analytic rank are equivalent over large fields, Spectral norm of a symmetric tensor and its computation, Spectral equivalence of smooth group schemes over principal ideal local rings, Distinct Distances on Algebraic Curves in the Plane, Partial differential Chow forms and a type of partial differential Chow varieties, Sparse difference resultant, On the number of zero-patterns of a sequence of polynomials, Elimination of unknowns for systems of algebraic differential-difference equations, Bounds on the torsion subgroups of Néron–Severi groups, 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, A Gröbner free alternative for polynomial system solving, Kronecker's and Newton's approaches to solving: a first comparison, Improved explicit estimates on the number of solutions of equations over a finite field, Back-and-forth systems for generic curves and a decision algorithm for the limit theory, On the complexity of the resolvent representation of some prime differential ideals, Computing bases of complete intersection rings in Noether position, Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel, Effective differential Nullstellensatz for ordinary DAE systems with constant coefficients, On computing absolutely irreducible components of algebraic varieties with parameters, Degree and Dimension Estimates for Invariant Ideals of $$P$$ -Solvable Recurrences, Puiseux Expansions and Nonisolated Points in Algebraic Varieties, Effective definability of Kolchin polynomials, Sur la complexité du principe de Tarski-Seidenberg, Effective de Rham cohomology — The general case, The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree, Unnamed Item, Finding connected components of a semialgebraic set in subexponential time, Unnamed Item, 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, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Free-Form Modeling in Bilateral Brep and CSG Representation Schemes, WELL-FORMED SET REPRESENTATIONS OF SOLIDS, Poisson algebras via model theory and differential-algebraic geometry, Shifted varieties and discrete neighborhoods around varieties, Complexity results for triangular sets, Irreducibility of multivariate polynomials, On the efficiency of effective Nullstellensätze, Counting critical formations on the circle: algebraic-geometric and Morse-theoretic bounds, Complexity of stratifications of semi-Pfaffian sets, The complexity of linear problems in fields, A bibliography of quantifier elimination for real closed fields, Bounds of traces in complete intersections and degrees in the Nullstellensatz, Lower bounds for diophantine approximations, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz, Generalized polar varieties: geometry and algorithms, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, A Pommaret bases approach to the degree of a polynomial ideal, Lower bounds for arithmetic networks. II: Sum of Betti numbers, On the affine Bezout inequality, Solving systems of polynomial inequalities in subexponential time, Real quantifier elimination is doubly exponential, Semi-algebraic decision complexity, the real spectrum, and degree, Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, Straight-line programs in geometric elimination theory, On the order of approximation in approximative triadic decompositions of tensors, Effective differential Lüroth's theorem, Polynomial bound on the local Betti numbers of a real analytic germ, Improved complexity bounds for counting points on hyperelliptic curves, Configurations of lines in space and combinatorial rigidity, Computation of differential Chow forms for ordinary prime differential ideals, The number of reducible space curves over a finite field, Effective uniform bounding in partial differential fields, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, On the value set of small families of polynomials over a finite field. I, The dimension growth conjecture, polynomial in the degree and without logarithmic factors, An incidence theorem in higher dimensions, Complexity of triangular representations of algebraic sets, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Complexity of computations in Commutative Division of the USSR Academy of Sciences, Bit-size estimates for triangular sets in positive dimension, Polar varieties, Bertini's theorems and number of points of singular complete intersections over a finite field, Variety evasive sets, Using elimination theory to construct rigid matrices, Equations for the projective closure and effective Nullstellensatz, On the bit complexity of polynomial system solving, Time-space tradeoffs in algebraic complexity theory, Deformation techniques for efficient polynomial equation solving., The complexity of local dimensions for constructible sets, 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, Explicit estimates for the number of rational points of singular complete intersections over a finite field, The dynamical Mordell-Lang problem for Noetherian spaces, Deciding consistency of systems of exponential-polynomial inequalities in subexponential time, Estimates on the number of \(\mathbb{F}_q\)-rational solutions of variants of diagonal equations over finite fields, Elimination for generic sparse polynomial systems, Distinct distances on curves via rigidity, Intrinsic complexity estimates in polynomial optimization, Polynomial bounds for invariant functions separating orbits, Evaluating geometric queries using few arithmetic operations, Counting connected components of a semialgebraic set in subexponential time, Complexity of solving parametric polynomial systems, Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem, Implicitization of rational parametric equations, On sign conditions over real multivariate polynomials, On the geometry of polar varieties, A parametric representation of totally mixed Nash equilibria, Probabilistic algorithms for computing resolvent representations of regular differential ideals, Complexity of deciding the first-order theory of real closed fields, Properness defects of projection and minimal discriminant variety, On Bézout inequalities for non-homogeneous polynomial ideals, A linear algebra approach to the differentiation index of generic DAE systems, Lower bounds for arithmetic networks, An algorithm for implicit interpolation, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, Complexity of deciding Tarski algebra, Factorization patterns on nonlinear families of univariate polynomials over a finite field, On the parallel complexity of the polynomial ideal membership problem, Topology of generic multijet preimages and blow-up via Newton interpolation, Lower bound for the approximative complexity, Complexity bounds in elimination theory -- a survey., On the complexity of counting components of algebraic varieties, On the number of sets definable by polynomials, Trajectories of polynomial vector fields and ascending chains of polynomial ideals, A sparse effective Nullstellensatz, Effective difference elimination and nullstellensatz, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Bounds on the torsion subgroup schemes of Néron-Severi group schemes, Functional programming concepts and straight-line programs in computer algebra, Degeneracy loci and polynomial equation solving, Bit complexity for computing one point in each connected component of a smooth real algebraic set, Construction of roadmaps in semi-algebraic sets, Solving systems of polynomial inequalities over a real closed field in subexponential time, Complexity of factoring and calculating the GCD of linear ordinary differential operators, Effective equidimensional decomposition of affine varieties, On the number of points of algebraic sets over finite fields, Transfer theorems via sign conditions, How to compute the Chow form of an unmixed polynomial ideal in single exponential time, Sparse differential resultant for Laurent differential polynomials, Multilevel polynomial partitions and simplified range searching, On the number of solutions of systems of certain diagonal equations over finite fields, Systems of rational polynomial equations have polynomial size approximate zeros on the average, A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:798314&oldid=12722007"