Polar varieties and efficient real elimination

Let S-0 be a smooth and compact real variety given by a reduced regular seq uence of polynomials f(1) , . . . , f(p). This paper is devoted to the algo rithmic problem of finding efficiently a representative point for each conn ected component of S-0. For this purpose we exhibit explicit polynomial equ ations that describe the generic polar varieties of S-0. This leads to a pr ocedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) description length of the input equations f(1) , . . . , f( p) and in a suitably introduced, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system f(1) , . . . , f(p).