The non-scalar Model of Complexity in Computational Geometry

An outline on the relation between algebraic complexity theories and semialgebraic sets is presented. First we discuss the concepts of total and non-scalar complexities both for polynomials and semialgebraic sets observing that they are ”geometric complexities” verifying the ”semialgebraic” version of the Benedetti-Risler conjecture [4]. Moreover, we remark that total and non-scalar complexities of semialgebraic sets are decidable theories. Finally, using non-scalar complexity and intersection numbers of semialgebraic sets we get new lower bounds for several problems in computational geometry, generalizing the results obtained by M. Ben-Or using total complexity and number of connected components. An expanded version of the ideas sketched here is [10]