The complexity of elementary algebra and geometry

DOI10.1016/0022-0000(86)90029-2zbMath0634.03031OpenAlexW2006918089MaRDI QIDQ1096620

Michael Ben-Or, John H. Reif, Dexter Kozen

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90029-2

zbMATH Keywords

quantifier elimination semialgebraic sets exponential space NC circuit theory of real closed fields

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Semialgebraic sets and related spaces (14P10)

Related Items

A polynomial solution for the Potato-peeling problem, Reasoning about probabilistic sequential programs, Rational Points and Trace Forms on a Finite Algebra over a Real Closed Field, On the complexity of some basic problems in computational convexity. I. Containment problems, On maps which preserve semipositivity and quantifier elimination theory for real numbers, A bibliography of quantifier elimination for real closed fields, Polar varieties, real equation solving, and data structures: the hypersurface case, On computing a set of points meeting every cell defined by a family of polynomials on a variety, Real quantifier elimination is doubly exponential, A polynomial-time algorithm for the topological type of real algebraic curve, Parallel computational geometry, Algebraic decomposition of regular curves, Note on the computational complexity of $j$-radii of polytopes in $\mathbb R^ n$, Finitely representable databases, On the complexity of $p$-adic basic semi-algebraic sets, Parametric Markov chains: PCTL complexity and fraction-free Gaussian elimination, Bisimilarity of Diagrams, Queries with arithmetical constraints, Reachability and connectivity queries in constraint databases, Between the Rings $${\mathbb Z}/p^n{\mathbb Z}$$ and the Ring $${\mathbb Z}_p$$: Issues of Axiomatizability, Definability and Decidability, Linear constraint query languages expressive power and complexity, Condition number based complexity estimate for solving polynomial systems, Classifying the computational complexity of problems, Linear solving for sign determination, Tarski’s Influence on Computer Science, Unnamed Item, A uniform method for proving lower bounds on the computational complexity of logical theories, Existence and uniqueness of the real closure of an ordered field without Zorn's lemma, 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 computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination, On information invariants in robotics, The complexity of deciding consistency of systems of polynomials in exponent inequalities, Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces, Computational complexity of determining which statements about causality hold in different space-time models, Detecting cusps and inflection points in curves, Deciding consistency of systems of exponential-polynomial inequalities in subexponential time, NC algorithms for real algebraic numbers, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Counting connected components of a semialgebraic set in subexponential time, A parametric representation of totally mixed Nash equilibria, Complexity of deciding the first-order theory of real closed fields, Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, Algebraic optimization: The Fermat-Weber location problem, The uniform measure of simple regular sets of infinite trees, Solving degenerate sparse polynomial systems faster, Computing Amoebas, Sur la complexité du principe de Tarski-Seidenberg, A logic for reasoning about probabilities, Complexity of computation on real algebraic numbers, Generic computation of the real closure of an ordered field., Dynamic evaluation and real closure., A ModalWalk Through Space, Querying spatial databases via topological invariants, Unnamed Item, Real addition and the polynomial hierarchy, Parallel algorithms for matrix normal forms, Solving systems of polynomial inequalities over a real closed field in subexponential time, Computation of equilibria in noncooperative games

Cites Work