Verification complexity of linear prime ideals

AbstractThe topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset X ⊆ Rm where R is a real or algebraically closed field. We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of linear type generalizing a result by Winograd (1970). As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms:For deciding whether a number is a zero of several polynomials—if this number and the coefficients of these polynomials are given as input data—evaluation of each polynomial with Horner's rule and then testing the values for zero is optimal.For verifying that a vector satisfies a system of linear equations—given the vector and the coefficients of the system as input data—the natural algorithm is optimal