Editing Algebraic geometry (section)

===Cylindrical algebraic decomposition (CAD)===
CAD is an algorithm which was introduced in 1973 by G. Collins to implement with an acceptable complexity the [[Tarski–Seidenberg theorem]] on [[quantifier elimination]] over the real numbers.

This theorem concerns the formulas of the [[first-order logic]] whose [[atomic formula]]s are polynomial equalities or inequalities between polynomials with real coefficients. These formulas are thus the formulas which may be constructed from the atomic formulas by the logical operators ''and'' (∧), ''or'' (∨), ''not'' (¬), ''for all'' (∀) and ''exists'' (∃). Tarski's theorem asserts that, from such a formula, one may compute an equivalent formula without quantifier (∀, ∃).

The complexity of CAD is doubly exponential in the number of variables. This means that CAD allows, in theory, to solve every problem of real algebraic geometry which may be expressed by such a formula, that is almost every problem concerning explicitly given varieties and semi-algebraic sets.

While Gröbner basis computation has doubly exponential complexity only in rare cases, CAD has almost always this high complexity. This implies that, unless if most polynomials appearing in the input are linear, it may not solve problems with more than four variables.

Since 1973, most of the research on this subject is devoted either to improving CAD or finding alternative algorithms in special cases of general interest.

As an example of the state of art, there are efficient algorithms to find at least a point in every connected component of a semi-algebraic set, and thus to test if a semi-algebraic set is empty. On the other hand, CAD is yet, in practice, the best algorithm to count the number of connected components.