Finding at least one point in each connected component of a real algebraic set defined by a single equation (Q5925972)

Let \(P\) be a \(n\)-variate polynomial with rational coefficients, defining an algebraic subset \(V\) of the real affine space \(\mathbb{R}^n\). The paper describes an implementable algorithm which decides whether \(V\) is empty. Otherwise the algorithm returns at least one (real algebraic) point of each connected component of \(V\). The authors claim that their algorithm has a low ``practical complexity''. However they admit that their algorithm does not meet the best known theoretical complexity bounds, at least in worst case. Nevertheless, there is no doubt that, after a suitable rearrangement, their procedure may compete in efficiency with known theoretical algorithms. In case that \(P\) is squarefree and \(V\) is a real hypersurface with only finitely many singularities, their complexity claim seems convincing. In case of infinitely many singularities of \(V\), the authors use a deformation of the equation \(P\) and this may spoil considerably the ``practical complexity'' of their procedure. The paper extends well known algorithmic critical point methods to the case \(V\) is not compact. In distinction to already existing, similar research in this field, the authors make no attempt to give definition of ``practical complexity'' in mathematical terms.