direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

Test complexity of generic polynomials
Zitatschlüssel BLS-Test-Complexity-Of-Generic-Polynomials
Autor Peter Bürgisser and Thomas Lickteig and Michael Shub
Seiten 203-215
Jahr 1992
DOI 10.1016/0885-064X(92)90022-4
Journal J. Compl.
Jahrgang 8
Nummer 3
Zusammenfassung We investigate the complexity of algebraic decision trees deciding membership in a hypersurface $X$ in $\mathbb C^m$. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurface $X$ in $\mathbb C^m$. Over the reals, where in addition to equality branching also $<$-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces $X$ in $\mathbb R^m$. In the case $m=1$ we give also a lower bound for finite subsets $X$ in $\mathbb R$.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe