Publication Details
Title: Verification Complexity of Linear Prime Ideals
Author: P. Buergisser and T. Lickteig
Group: ICSI Technical Reports
Date: July 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-039.pdf
Overview:
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 Information:
ICSI Technical Report TR-91-039
Bibliographic Reference:
P. Buergisser and T. Lickteig. Verification Complexity of Linear Prime Ideals. ICSI Technical Report TR-91-039, July 1991
Author: P. Buergisser and T. Lickteig
Group: ICSI Technical Reports
Date: July 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-039.pdf
Overview:
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 Information:
ICSI Technical Report TR-91-039
Bibliographic Reference:
P. Buergisser and T. Lickteig. Verification Complexity of Linear Prime Ideals. ICSI Technical Report TR-91-039, July 1991