Verification Complexity of Linear Prime Ideals

The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset X propersubset (R superscript 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 lineary type generalizing a result by Winograd [Win-70]. 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.

ICSI Technical Report TR-91-039

Technical Report