direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

Verification complexity of linear prime ideals
Zitatschlüssel BL-Verification-Complexity-Of-Linear-Prime-Ideals
Autor Peter Bürgisser and Thomas Lickteig
Seiten 247-267
Jahr 1992
Journal J. Pure Appl. Alg.
Jahrgang 81
Zusammenfassung 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.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe