Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V

Strong Version of the Basic Deciding Algorithm for the Existential Theory of Real Fields
Alexander Christov
[Download PostScript] [Download PDF]

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

Last Change: 08/18/99 at 13:00:38
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope