# Complexity of computations with definable sets.

Nicolai Vorobjov University of Bath 4pm Tuesday 14th March 2006 Room 2511, JCMB, King's Buildings

Consider sets in R^n defined by first-order formulae (with or without quantifiers) having atoms of the kind f>0, where each f is either a polynomial, or an algebraic function, or an elementary transcendental function, or, more generally, a real analytic Pfaffiann function. We will discuss upper complexity bounds for deciding topological properties and computing homological invariants of these sets, with applications to non-cooperative game theory and robotics. The technique behind the algorithms is closely related to the one used in estimates of sums of Betti numbers of definable sets, in terms of formats of their formulae, which is a classical question in real analytic geometry.