[an error occurred while processing this directive]
An error occured whilst processing this directive
Complexity of computations with definable sets.
University of Bath
4pm Tuesday 14th March 2006
Room 2511, JCMB, King's Buildings
Abstract
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.
An error occured whilst processing this directive