1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Add optimisation criterion $\max 1$ and you are good to go; the search for an admissable solution remains. $\endgroup$
    – Raphael
    Commented Oct 28, 2014 at 9:09
  • $\begingroup$ This is a Diophantine equation. $\endgroup$
    – Falk Hüffner
    Commented 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$
    – Tyler Durden
    Commented Oct 28, 2014 at 10:31

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is this true even if $m,x_i$ and $y_i$ can be BOTH positive and negative integers? $\endgroup$
    – Tyler Durden
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – Tyler Durden
    Commented 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$
    – Yuval Filmus
    Commented 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.