Quantifier Elimination by Cylindrical Algebraic Decomposition — Twenty Years of Progress

The CAD (cylindrical algebraic decomposition) method and its application to QE (quantifier elimination) for ERA (elementary real algebra) was announced by the author in 1973 at Carnegie Mellon University (Collins 1973b). In the twenty years since then several very important improvements have been made to the method which, together with a very large increase in available computational power, have made it possible to solve in seconds or minutes some interesting problems. In the following we survey these improvements and present some of these problems with their solutions.