Verification complexity of linear prime ideals. Bürgisser, P. & Lickteig, T. J. Pure Appl. Alg., 81:247-267, 1992.
The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset $X$ in $R^m$ 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.
@ARTICLE{BL-Verification-Complexity-Of-Linear-Prime-Ideals,
JOURNAL={J. Pure Appl. Alg.},
TITLE={Verification complexity of linear prime ideals},
URL={http://www.sciencedirect.com/science/article/pii/002240499290059O},
VOLUME={81},
AUTHOR={Peter Bürgisser and Thomas Lickteig},
YEAR={1992},
ABSTRACT={The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset $X$ in $R^m$ 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.},
PAGES={247-267}
}