Verification Complexity of Linear Prime Ideals

TitleVerification Complexity of Linear Prime Ideals
Publication TypeTechnical Report
Year of Publication1991
AuthorsBürgisser P, Lickteig TMichael
Other Numbers669

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.

Bibliographic Notes

ICSI Technical Report TR-91-039

Abbreviated Authors

P. Buergisser and T. Lickteig

ICSI Publication Type

Technical Report