Chistov, Alexander Leonidovich

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

English, Russian
LATEX 2e

Email address: sliss@iias.spb.su

Series: St. Petersburg Mathematical Society Preprints
To be submitted to Zapiski Nauchnych Semin. POMI

Abstract:

Let $U$ be a real algebraic set in $n$--dimensional affine space which is given
as a set of zeros of a family of polynomials of degrees less than $d$. Let
$U_i$, $i\in I$ be the family of all irreducible components of $U$. Let
$U_i^{(s)}$ be the closure in the classical topology of the set of all smooth
points of dimension $s$ of $U_i$. In the paper an algorithm is described for
constructing a finite set $S$ of points of $U$ which has a non--empty
intersection with every connected component of every $U_i^{(s)}$  for every
$i\in I$, $0\le s\le n$. The number of points of $S$ is bounded from above by a
polynomial in $d^n$. The similar result is valid for basic semi--algebraic
sets. The working time of the algorithm (for the case of algebraic varieties)
is polynomial in the size of input and $d^n$. More precise formulations are
given below involving triangulations of $U$ if $U$ is bounded (respectively of
the Alexandrov compactification of $U$ if $U$ is not bounded).