Publication Details
Title: Test Complexity of Generic Poynomials
Author: P. Buergisser, T. Lickteig, and M. Shub
Group: ICSI Technical Reports
Date: July 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-038.pdf
Overview:
We investigate the complexity of algebraic decision membership in a hypersurface X propersubset (C superscript 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 subsurface X propersubset (C superscript m). In the situation over the reals where in addition to equality branching also leq-branching allowed, we prove an analogous statement for irreducible "generic" hypersurfaces X propersubset (R superscript m). In the case m=1 we give also a lower bound for finite subsets of X propersubset R.
Bibliographic Information:
ICSI Technical Report TR-91-038
Bibliographic Reference:
P. Buergisser, T. Lickteig, and M. Shub. Test Complexity of Generic Poynomials. ICSI Technical Report TR-91-038, July 1991
Author: P. Buergisser, T. Lickteig, and M. Shub
Group: ICSI Technical Reports
Date: July 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-038.pdf
Overview:
We investigate the complexity of algebraic decision membership in a hypersurface X propersubset (C superscript 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 subsurface X propersubset (C superscript m). In the situation over the reals where in addition to equality branching also leq-branching allowed, we prove an analogous statement for irreducible "generic" hypersurfaces X propersubset (R superscript m). In the case m=1 we give also a lower bound for finite subsets of X propersubset R.
Bibliographic Information:
ICSI Technical Report TR-91-038
Bibliographic Reference:
P. Buergisser, T. Lickteig, and M. Shub. Test Complexity of Generic Poynomials. ICSI Technical Report TR-91-038, July 1991