On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
From MaRDI portal
Publication:1185458
DOI10.1016/S0747-7171(10)80005-7zbMath0798.68073OpenAlexW2001255903MaRDI QIDQ1185458
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)80005-7
parallel computationquantifier eliminationcomplexity analysisdecision methodbit model of computationfirst order theory of the realsreal number model of computation
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
The theory of Liouville functions, Finding irreducible components of some real transcendental varieties, Separation of complexity classes in Koiran's weak model, P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\), The complexity to compute the Euler characteristic of complex varieties, Real quantifier elimination for the synthesis of optimal numerical algorithms (case study: square root computation), On maps which preserve semipositivity and quantifier elimination theory for real numbers, A note on the computation of the CP-rank, Generalized polar varieties: geometry and algorithms, Interval Linear Algebra and Computational Complexity, 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, Rectilinear shortest paths in the presence of rectangular barriers, A polynomial-time algorithm for computing low CP-rank decompositions, Complexity lower bounds for computation trees with elementary transcendental function gates, Polynomial equation solving by lifting procedures for ramified fibers, Finitely representable databases, Matrices of Bounded Psd Rank are Easy to Detect, Bounding the radii of balls meeting every connected component of semi-algebraic sets, Computability of a map and decidability of its graph in the model of Blum, Shub and Smale, On the complexity of quantified linear systems, Queries with arithmetical constraints, The Complexity of Drawing Graphs on Few Lines and Few Planes, Faster real root decision algorithm for symmetric polynomials, Hardness of embedding simplicial complexes in \(\mathbb R^d\), The smallest mono-unstable convex polyhedron with point masses has 8 faces and 11 vertices, The complexity of the Hausdorff distance, Equivalence of state representations for hidden Markov models, Quantifier elimination theory and maps which preserve semipositivity, Fast simplifications for Tarski formulas based on monomial inequalities, Variant quantifier elimination, Computing with Tarski formulas and semi-algebraic sets in a web browser, Open weak CAD and its applications, Equilibria, fixed points, and complexity classes, Equivalence checking of quantum finite-state machines, Constraint Satisfaction Problems over Numeric Domains, Homogeneous multivariate polynomials with the half-plane property, Quantum automata and algebraic groups, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, An elementary proof of Sylvester's double sums for subresultants, The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete., The \(\mathcal A\)-truncated \(K\)-moment problem, A complexity perspective on entailment of parameterized linear constraints, A weak version of the Blum, Shub, and Smale model, Hybrid Automata in Systems Biology: How Far Can We Go?, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Computational complexity of determining which statements about causality hold in different space-time models, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game, Grid methods in computational real algebraic (and semialgebraic) geometry, Finding at least one point in each connected component of a real algebraic set defined by a single equation, Intrinsic complexity estimates in polynomial optimization, Language equivalence of probabilistic pushdown automata, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Hybrid automata, reachability, and systems biology, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Computational complexity of diagram satisfaction in Euclidean geometry, An Almost Optimal Algorithm for Computing Nonnegative Rank, Back-and-forth systems for generic curves and a decision algorithm for the limit theory, Macaulay style formulas for sparse resultants, Improved projection for cylindrical algebraic decomposition, Explicit formulas for the multivariate resultant., Automatic derivation of probabilistic inference rules, Approximating the minimum rank of a graph via alternating projection, Periodic generalized automata over the reals, A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, Some lower bounds for the complexity of the linear programming feasibility problem over the reals, Inclusion dynamics hybrid automata, Cylindrical algebraic decomposition using local projections, Factoring a band matrix over a semiring, Computing roadmaps of semi-algebraic sets on a variety, Trace Refinement in Labelled Markov Decision Processes, Matrices in elimination theory, Computing a Nonnegative Matrix Factorization---Provably, \(\delta\)-uniform BSS machines, Unnamed Item, Exact Algorithms for Linear Matrix Inequalities, Counting problems over the reals, An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms, Quantifier elimination for trigonometric polynomials by cylindrical trigonometric decomposition, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Saturation and stability in the theory of computation over the reals, A complexity theory of constructible functions and sheaves, Special algorithm for stability analysis of multistable biological regulatory systems, On extremal graphs for zero forcing number, Une borne optimale pour la programmation entière quasi-convexe, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Description of the connected components of a semialgebraic set in single exponential time, Decidable verification for reducible timed automata specified in a first order logic with time, Real solving for positive dimensional systems., Computation of equilibria in noncooperative games
Cites Work
