What is the Computational Complexity of Mathematica's CylindricalDecomposition

Question

Mathematica' CylindricalDecomposition implements an algorithm known as Cylindrical Algebraic Decomposition. Wolfram MathWorld's article on Cylindrical Algebraic Decomposition says that this algorithm "becomes computationally infeasible for complicated inequalities."

Can this statement be made more precise? Specifically, how does the time and space relate to the degree and number of variables of the multivariate polynomials? Does the time and space depend on other parameters?

Answer 1

Tarski showed that for every formula including quantifiers there is always an equivalent quantifier free formula. Obtaining the latter from the former is called quantifier elimination. (...)

In particular, for the cylindrical algebraic decomposition (CAD), the number of operations usually scales in a doubly exponential fashion with the number of variables, while the newer methods are doubly exponential in the number of quantifier alternations.

Reference: MIT 6.972 Algebraic techniques and semidefinite optimization by Pablo A. Parrilo

Edit: A nice article on Mma CAD algorithms here