What is the computational complexity of a Mathematica cylindrical decomposition?

Question

Mathematica ' CylindricalDecomposition implements an algorithm known as Cylindrical Algebraic Decomposition. In a Wolfram MathWorld article on Cylindrical Algebraic Decomposition , this algorithm "becomes more complicated for complex inequalities."

Can this statement be clarified? In particular, how is time and space related to the degree and number of variables of multidimensional polynomials? Does time and space depend on other parameters?

Answer 1

Tarski showed that for every formula that includes quantifiers, there is always an equivalent quantum free formula. Getting the last of the first is called quantification. (...)

In particular, for cylindrical algebraic decomposition (CAD), the number of operations usually scales twice exponentially with the number of variables, while newer methods are twice exponential in the number of quantized alternations.

Ref: MIT 6.972 Algebraic Methods and Semi-Optimal Optimization by Pablo A. Parrilo

Edit : a good article on MMA CAD algorithms here