ABSTRACT: We report on ongoing research joint with F. Cucker (CityU, Hong Kong) to classify the complexity to compute basic topological invariants of (semi-) algebraic sets. A version of Valiant's counting complexity class #P, adapted to the Blum-Shub-Smale model of computations over the reals, seems to provide the right framework for this. We first present our results for the restricted model of additive computations over the reals, which can be grouped into two kinds: structural relationships between complexity classes and completeness results. A particularly interesting consequence of our work is that the computation of the Euler characteristic is easier than the computation of a single Betti number (e.g., the number of connected components), under standard complexity theoretic assumptions (#P versus PSPACE). Then we discuss preliminary completeness results for the unrestricted model of computation related to the computation of the geometric degree and the Euler characteristic.