Duality methods for the membership problem
Alicia Dickenstein, Carmen Sessa · Birkhäuser Boston eBooks · 1991
The classical problem of deciding membership to arbitrary polynomial ideals is EXPSPACE complete. Moreover, the problem of finding a representation of a polynomial by generators of a given ideal may involve doubly exponential (in the number of variables) degrees ([16]). The same difficulty arises when computing Gröebner bases of arbitrary polynomial ideals ([11]). This means that all known techniques to decide membership and to find representations of polynomials with respect to a given ideal lead to doubly exponential (sequential time) worst case complexities. However, if the geometry of the underlying algebraic variety is particularly simple, e.g. if the given ideal is zero dimensional or complete intersection, algorithms of considerably lower complexity can be found (see e.g. [7], [9]). The improvements are due to recent progress concerning affine versions of the effective Nullstellensatz (compare [18] and the references given there). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.