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

DOI10.1016/S0747-7171(10)80003-3zbMath0763.68042OpenAlexW1991813962MaRDI QIDQ1185456

Publication date: 28 June 1992

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0747-7171(10)80003-3

zbMATH Keywords

quantifier elimination decision problem complexity of elementary algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Semialgebraic sets and related spaces (14P10) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (only showing first 100 items - show all)

On the decidability of reachability in continuous time linear time-invariant systems ⋮ Beyond the Existential Theory of the Reals ⋮ Bounding and computing obstacle numbers of graphs ⋮ On robustness for the Skolem, positivity and ultimate positivity problems ⋮ Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations ⋮ The parametrized complexity of the segment number ⋮ Computing the density of the positivity set for linear recurrence sequences ⋮ Graphs of intersections of closed polygonal chains ⋮ Learning from rounded-off data. ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Formulation of linear problems and solution by a universal machine ⋮ On the complexity of quadratic programming in real number models of computation ⋮ Discrete semantics for hybrid automata. Avoiding misleading assumptions in systems biology ⋮ Local rules for pentagonal quasi-crystals ⋮ On the planar piecewise quadratic 1-center problem ⋮ A potential reduction algorithm for two-person zero-sum mean payoff stochastic games ⋮ Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints ⋮ Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers ⋮ On maps which preserve semipositivity and quantifier elimination theory for real numbers ⋮ Interval Linear Algebra and Computational Complexity ⋮ Blind algebraic identification of communication channels: symbolic solution algorithms ⋮ Symbolic computation in hyperbolic programming ⋮ The saddle point problem of polynomials ⋮ The exact region of stability for MacCormack scheme ⋮ The complexity of reachability in parametric Markov decision processes ⋮ Parametric probabilistic transition systems for system design and analysis ⋮ Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraints ⋮ Minimizing the sum of linear fractional functions over the cone of positive semidefinite matrices: approximation and applications ⋮ Unnamed Item ⋮ Conormal spaces and Whitney stratifications ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities ⋮ A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem ⋮ An unfeasibility view of neural network learning ⋮ The complexity of the Hausdorff distance ⋮ Quantifier elimination theory and maps which preserve semipositivity ⋮ Root isolation of zero-dimensional polynomial systems with linear univariate representation ⋮ How Do Exponential Size Solutions Arise in Semidefinite Programming? ⋮ Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces ⋮ Unnamed Item ⋮ Numerically computing real points on algebraic sets ⋮ Relational hidden variables and non-locality ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ Unnamed Item ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Out of order quantifier elimination for standard quantified linear programs ⋮ Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time ⋮ Computing the first Betti number of a semi-algebraic set ⋮ On the Computational Complexity of Degenerate Unit Distance Representations of Graphs ⋮ On Probabilistic Parallel Programs with Process Creation and Synchronisation ⋮ Deformation techniques for efficient polynomial equation solving. ⋮ Computing the homology of real projective sets ⋮ On the Complexity of Reachability in Parametric Markov Decision Processes ⋮ Proving inequalities and solving global optimization problems via simplified CAD projection ⋮ Termination of polynomial loops ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ On the computation of Boolean functions by analog circuits of bounded fan-in ⋮ FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension ⋮ On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data ⋮ A search-based procedure for nonlinear real arithmetic ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ On projections of semi-algebraic sets defined by few quadratic inequalities ⋮ Decomposition plans for geometric constraint systems. I: Performance measures for CAD ⋮ A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF ⋮ A Gröbner free alternative for polynomial system solving ⋮ Minimizing polynomials via sum of squares over the gradient ideal ⋮ On sign conditions over real multivariate polynomials ⋮ The computational complexity of some problems of linear algebra ⋮ Recurrence with affine level mappings is P-time decidable for CLP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Properness defects of projection and minimal discriminant variety ⋮ A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games ⋮ Inclusion dynamics hybrid automata ⋮ Coloring \(d\)-embeddable \(k\)-uniform hypergraphs ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ A Matrix Positivstellensatz with Lifting Polynomials ⋮ On the computational complexity of decision problems about multi-player Nash equilibria ⋮ Realizability of polytopes as a low rank matrix completion problem ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ First-order orbit queries ⋮ Positive semidefinite rank ⋮ Worst-case results for positive semidefinite rank ⋮ Deciding probabilistic bisimilarity distance one for probabilistic automata ⋮ Exotic quantifiers, complexity classes, and complete problems ⋮ Quantifier elimination by cylindrical algebraic decomposition based on regular chains ⋮ Quadric Arrangement in Classifying Rigid Motions of a 3D Digital Image ⋮ On Searching for Small Kochen-Specker Vector Systems ⋮ Interactive proofs and a Shamir-like result for real number computations ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Untangling a planar graph ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Complexity of computing the local dimension of a semialgebraic set ⋮ Querying spatial databases via topological invariants

Cites Work

This page was built for publication: 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