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

Recently several theoretical single exponential time algorithms (in the number of variables) have been proposed for deciding the existential theory of reals. These algorithms have from a complexity analysis point of view a much better behaviour than CAD which was doubly exponential in the number of variables, but an efficient implementation based on these new ideas has never been performed yet. This paper is devoted to the development of the following idea «it is possible to implement efficiently slight variants of single exponential methods well adapted to important particular cases of the decision problem». We explain the main ideas, propose more efficient versions of the methods and make concrete propositions for future experiments