The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals
Dung T. Huynh · SIAM Journal on Computing · 1986
This paper shows that the membership problems for two subclasses of polynomial ideals are NP-hard. The first subclass is defined by bounding the number of variables ($ \leqq 4$), whereas the second is defined by considering polynomials of the form $Y - M$, where Y is a variable and M is a monomial.