Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

Dima Grigoriev, Dmitrii V. Pasechnik

Given a quadratic map Q : K^n -> K^k defined over a computable subring D of a real closed field K, and a polynomial p(Y_1,...,Y_k) of degree d, we consider the zero set Z=Z(p(Q(X))…