On the Theoretical and Practical Complexity of the Existential Theory of Reals

DOI10.1093/COMJNL/36.5.427zbMath0780.68058OpenAlexW2007438578MaRDI QIDQ3140553

Pablo Solernó, Joos Heintz, Marie-Françoise Roy

Publication date: 1993

Published in: The Computer Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/comjnl/36.5.427

zbMATH Keywords

cylindrical algebraic decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25)

Related Items (11)

Automatic computation of the complete root classification for a parametric polynomial ⋮ SMT-RAT: An Open Source C++ Toolbox for Strategic and Parallel SMT Solving ⋮ VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities ⋮ Faster real root decision algorithm for symmetric polynomials ⋮ Decision algorithms for fragments of real analysis. I: Continuous functions with strict convexity and concavity predicates ⋮ Proving inequalities and solving global optimization problems via simplified CAD projection ⋮ Finding at least one point in each connected component of a real algebraic set defined by a single equation ⋮ Properness defects of projection and minimal discriminant variety ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ Efficient Simplification Techniques for Special Real Quantifier Elimination with Applications to the Synthesis of Optimal Numerical Algorithms ⋮ Real solving for positive dimensional systems.

This page was built for publication: On the Theoretical and Practical Complexity of the Existential Theory of Reals