Polynomial-time computing over quadratic maps i: sampling in real algebraic sets (Q1781114)

The authors present an algorithmic method for computing a set of sampling points in \(\mathbb{K}^n\), where \(\mathbb{K}\) is a real closed field, intersecting nontrivially each connected component of a zero set in \(\mathbb{K}^n\), defined over a computable subring \(D\) of \(\mathbb{K}^n\) by means of a quadratic map \(Q:=\mathbb{K}^n\mapsto\mathbb{K}^k\) and a \(k\)-variate polynomial \(p\) over \(D\). The authors prove that the procedure works in \((dn)^{O(k)}\) arithmetic operations in \(D\), where \(d\) is the degree of \(p\). The process consists of exact symbolic computations in \(D\), involving the extension of \(\mathbb{K}\) by means of infinitesimals.