Test Complexity of Generic Poynomials

TitleTest Complexity of Generic Poynomials
Publication TypeTechnical Report
Year of Publication1991
AuthorsBürgisser, P., Lickteig T. Michael, & Shub M.
Other Numbers668

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 Notes

ICSI Technical Report TR-91-038

Abbreviated Authors

P. Buergisser, T. Lickteig, and M. Shub

ICSI Publication Type

Technical Report