
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1998  Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V  
85185

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 nonempty intersection with every connected component of dimension $s$ of every irreducible component of $U^{(s)}$. The similar result is valid for basic real semialgebraic 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
English 
Universität Bonn > Institut für Informatik > Abteilung V 