Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is the following equation an instance of an integer linear program (ILP):

$ (x_1\cdot y_1) + (x_1\cdot y_1) + \cdots + (x_{n-1}\cdot y_{n-1}) + (x_n\cdot y_n) = m $ i.e. is there an assignment of variables $y_i$ such that the equation is true? After googling around I noticed that ILPs usually involve maximising or minimising a variable, but that is not what is needed here. If not, could anyone tell me what type of problem this is and if there are any known complexity results?

  • 1
    $\begingroup$ Add optimisation criterion $\max 1$ and you are good to go; the search for an admissable solution remains. $\endgroup$
    – Raphael
    Oct 28, 2014 at 9:09
  • $\begingroup$ This is a Diophantine equation. $\endgroup$ Oct 28, 2014 at 9:15
  • $\begingroup$ thanks @FalkHüffner, i found a similar question here: cs.stackexchange.com/questions/29254/… seems like they are solvable in P-Time $\endgroup$ Oct 28, 2014 at 10:31

1 Answer 1


Your problem has a solution if and only if $m$ is a multiple of the greatest common divisor of $x_1,\ldots,x_n$. You can compute the GCD in polynomial time using the Euclidean algorithm (the version where you divide in each step rather than subtract) applied $n-1$ times.

  • $\begingroup$ Is this true even if $m,x_i$ and $y_i$ can be BOTH positive and negative integers? $\endgroup$ Nov 12, 2014 at 10:26
  • $\begingroup$ Yes, and in fact you have to allow the $y_i$ to be positive, negative, or zero. Otherwise this criterion is not correct. $\endgroup$ Nov 12, 2014 at 15:15
  • $\begingroup$ My apologies, but i actually got my criteria wrong. I have updated the answer - the variables are now limited to N instead of Z. I assume that the GCD mechanism no longer works? $\endgroup$ Nov 20, 2014 at 18:01
  • $\begingroup$ This is related to the coin problem (en.wikipedia.org/wiki/Coin_problem). It's better if you rolled back your change and asked a new question, so that this answer remains relevant. $\endgroup$ Nov 20, 2014 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.