Let $A$ be a matrix with integer coefficients and let $\vec c$ be a vector of integers. Is there an efficient algorithm to determine if $A\vec x=\vec c$ has a solution $\vec x$ consisting of nonnegative integers? If so, can the algorithm be improved if the entries of $A$ and $\vec c$ are nonnegative?
My motivation is to determine whether certain monomials in the ring $\Bbb C[x_1,\dotsc,x_n]$ graded by the matrix $A$ exist.
Hmmm... forgot about the non-negative.
Assuming $A$ is not already square and symmetric, try $$ A^T A x = A^T c. $$ At this point, $A^T A$ is symmetric positive semi-definite. If it is also positive definite, you can then ask whether $A^T c$ is in the integer lattice defined by $A^TA.$ Given all the attention to lattice reduction algorithms such as LLL, I would guess there are very good lattice membership algorithms available; I will see what I can find. If not, this is still a finite check and is easy enough for small $n.$
http://cs.nyu.edu/courses/spring13/CSCI-GA.3033-013/lectures/lecture-2.pdf
recommends A. Schrijver Theory of Linear and Integer Programming