1
$\begingroup$

Input

We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers $\ B :=$ {$\ b_1, ..., b_m$}

Desired Output

Return true if there exists a linear combination $\ a_1v_1 + a_2v_2 + ... + a_nv_n$ such that the resulting vector uses the integers $\ b_1, ... , b_m $ the same number of times that each occurs in B. Return false otherwise.

Example

Let $\ v_1 = (1,0,0,1), v_2 = (1,0,1,0) $ and $\ B =$ {$\ 0,4,2,2$}. Here the algorithm should return true since we can write $\ (4,0,2,2)$ as $\ 2v_1 + 2v_2$.

As another example, consider the same vectors with the integers {1,2,3,4}. Here we want to return false since we will never be able to write four strictly positive numbers as a linear combination of the two vectors.

So my questions are: What kind of problem is this? Can anyone prove it NP-complete or find a reasonable algorithm for it?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Welcome to CS.SE! If we also required $a_i \in \{0,1\}$, it'd be NP-hard by reduction from exactly-1-in-3 positive 3-SAT: consider a positive 3-CNF formula with $m$ clauses and $n$ variables, and associate to each variable $x_i$ a basis element $v_i$ that is $1$ in its $j$th column if $x_i$ appears in the $j$th column, or 0 otherwise; then use the multiset $B=\{1,1,\dots,1\}$. The formula has a exactly-1-in-3 satisfying assignment iff there is a subset of basis elementsthat sums to $(1,1,\dots,1)$. $\endgroup$ – D.W.♦ Sep 4 '17 at 4:18
  • $\begingroup$ It's easy to check if the $v_i$ are linearly independent. If they are the answer is trivially yes, for any order of $B$. If not, we know nothing per se; but maybe one can reduce the problem? $\endgroup$ – Raphael♦ Sep 4 '17 at 7:17
  • $\begingroup$ Thanks D.W., that does in fact appear to show that the problem is NP hard. $\endgroup$ – Kevin Sep 4 '17 at 22:16
  • $\begingroup$ I don't think that it shows that your problem is NP-hard, because your problem allows the $a_i$ to be any integer, not restricted to 0 or 1. It's possible that this might make the problem easier (at least, I don't see how to rule that out). $\endgroup$ – D.W.♦ Sep 5 '17 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.