Strong version of the basic deciding algorithm for the existential theory of real fields

A. L. Chistov

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part III, Tome 256 (1999), pp. 168-211

Résumé

Let $U$ be a real algebraic variety in $n$-dimensional affine space which is a set of all zeroes of a family of polynomials of degrees less than $d$. In the case when $U$ is bounded (it is the main case) an algorithm of polynomial complexity is described for constructing a subset of $U$ with the number of elements bounded from above by $d^n$ which for every $s$ has a non–empty intersection with every cycle with coefficients from ${\mathbb Z}/2{\mathbb Z}$ of dimension $s$ of the closure of the set of smooth points of dimension $s$ of $U$.