Let A be an nxn matrix of integers and b be an nx1 vector of integers.
Then, the problem:
"Does there exist a vector of nonnegative integers x such that Ax=b?"
is known to be NP-Complete.
Assume that a finite set of non-negative integers S is given, with at least 2 elements.
Then, the problem:
"Does there exist a vector of nonnegative integers x such that Ax=b, where all the elements of x are in S?"
seems to be harder than the first one in the sense that it looks like it is inapproximable within any constant positive factor.
Is there any reference for such results?
- Badges
- Science topic
- Similar topics
- Vectorization
More Yossi Peretz's questions See All
Similar questions and discussions