Test Complexity of Generic Poynomials
| Title | Test Complexity of Generic Poynomials |
| Publication Type | Technical Report |
| Year of Publication | 1991 |
| Authors | Bürgisser, P., Lickteig T. Michael, & Shub M. |
| Other Numbers | 668 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-91-038.pdf |
| Bibliographic Notes | ICSI Technical Report TR-91-038 |
| Abbreviated Authors | P. Buergisser, T. Lickteig, and M. Shub |
| ICSI Publication Type | Technical Report |