2
$\begingroup$

Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$:

$$ \begin{align*} L_0 &= [1,0,x] \\ L_1 &= [1,1,1] \\ L_2 &= [1,0,0] \\ L_3 &= [x,1,0] \\ L_4 &= [1,x,0] \end{align*} $$

I want to find all combinations of $m$ vectors (subsets of vectors from this list) whose elementwise sum in this combination will have exactly $m$ occurrences of $x$. Is there an algorithm to do this in less than $O(m^n)$ time?

In my example, if $m=2$, the only valid combination is $L_0 + L_4 = [1+1, 0+x, x+0] = [2, x, x]$. If $m=1$, valid answer is [$L_0$, $L_3$, $L_4$].

Key is: are there's any way to solve this problem without iterating over all $m^n$ combinations.

This might sound like an interview question, but in fact it is a task that I reduced my problem to.

$\endgroup$
  • $\begingroup$ Regarding NP-completeness, you can read the first chapter in part 3 (complexity theory) of Sipser's Introduction to the Theory of Computation. $\endgroup$ – Yuval Filmus Dec 14 '16 at 22:44
  • $\begingroup$ Please edit the question to incorporate any clarifications about the problem or about what question you want an answer to, then flag as 'obsolete' all comments that are no longer relevant. Thank you! $\endgroup$ – D.W. Dec 14 '16 at 23:08
  • $\begingroup$ I made a mistake in initial assesment - it's not $O(n!)$ but $O(m^n)$ complexety. $\endgroup$ – Akim Akimov Dec 14 '16 at 23:18
  • $\begingroup$ There have been a lot of changes to this question. Moreover, each edit has changed the problem in a fundamental way that invalidated prior answers. Please take more care to be precise about exactly what problem you want solved so we're not wasting our time describing a solution to a problem you don't care about. $\endgroup$ – D.W. Dec 15 '16 at 0:30
5
$\begingroup$

The question has changed. I'll answer the updated question. Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter values. I will assume that the vectors are from $\mathbb{R}^d$, i.e., $d$-dimensional vectors (in your example $d=3$).

Try all subsets

There are exactly ${n \choose m}$ subsets of $m$ vectors. You can try each, compute what its sum is, and count how many $x$'s it has. The running time will be $O(nd \cdot {n \choose m})$, and can be optimized to run in time $O(d \cdot {n \choose m})$. Note that ${n \choose m} \le 2^n$ and can be significantly smaller than $m^n$, so if we ignore the dependence on $d$, this is faster than your $O(m^n)$ time to beat.

Try all target vectors

Alternatively, we can try all possibilities for which $m$ locations (coordinates) in the sum contain a $x$. There are ${d \choose m}$ such possibilities. For each, we will try to find a subset of the input list whose sum has a $x$ in those special locations (coordinates), and no $x$ in any other location (coordinate). We'll temporarily ignore the requirement to have a subset of size exactly $m$.

Note that any valid solution must use only vectors that whose special coordinates all have entries from $\{0,x\}$ (in particular, no special coordinate can contain a $1$). (Any vector with a $1$ in any special coordinate can't be included in any valid combination; if it were included, the sum in that coordinate would be either $\ge x+1$ or $\le n$, according to whether we include any other vector with a $x$ in that coordinate or not.)

So, let's focus only on those $m$ coordinates, and ignore (throw away) all the others. In this way each $d$-vector is reduced to a $m$-vector. Then, we look for a subset of the input vectors that sums to the $m$-vector $[x,x,\dots,x]$. This is a multi-dimensional subset-sum problem. This particular subset-sum problem has a special form: it turns out to be an instance of the exact cover problem, and can be solved with standard algorithms for exact cover. The running time will be exponential in $m$. So, we'll solve the exact cover problem in $m$ dimensions, and then check each solution to see whether it is a valid solution to the original problem.

We repeat this ${d \choose m}$ times (once for each subset of $m$ coordinates). The running time to solve each instance of the $m$-dimensional exact cover problem is exponential in $m$, and we must solve ${d \choose m}$ of them, so the running time will be something in the vicinity of $O({d \choose m} \cdot 2^m)$.

Alternatively, given a target vector (a set of $m$ special coordinates), we could use integer linear programming to search for a subset of $m$ of the input vectors that sum to $[x,x,\dots,x]$ in those $m$ coordinates. This will again take time exponential in $m$, in the worst case, for each target vector, though in practice it might be faster. One nice thing about integer linear programming is that it lets you directly express the constraint that the subset must be of size $m$. Also, it may be fairly easy to implement this approach using an off-the-shelf ILP solver.

This algorithmic approach may be better or worse than the other schemes, depending on the values of $m,d$. If $m$ is very small or very close to $d$, this approach may be an improvement on the others.

Dynamic programming

There is a dynamic-programming algorithm whose running time is $O(nd \cdot 3^d)$. Basically, we have a table that keeps track of which $d$-dimensional vectors can be expressed as a sum of some subset of the input vectors.

Given an entry of a vector, we'll classify into one of three categories: $0$ (meaning the entry is $0$), $☹$ (meaning the entry is not $0$ and not $x$), and $x$ (meaning the entry is $x$). These have the obvious addition rules, e.g., $☹ + x = ☹$, $☹ + ☹ = ☹$, and so on. Thus, each vector mapped to a template where its entries are classified in this way; a template is a value $t \in \{0,☹,x\}^d$. A template stands for one or more vectors.

Now, for each template $t \in \{0,☹,x\}^d$, the table keeps track of whether any vector that matches the template $t$ can be reached by summing any subset of the input vectors. This table will have at most $3^d$ entries, since there are at most $3^d$ possible templates. You can fill in the entries of the table using dynamic programming in $O(nd \cdot 3^d)$ time. Finally, we check the table to see whether the template $[x,x,\dots,x]$ is expressible as a sum of input vectors. YAs described, this tells you whether any valid combination exists; you can augment this algorithm to keep track of all valid combinations.

This might be workable if $d$ is not too large; otherwise, it will be highly inefficient. It has the benefit of being not too difficult to implement, but it is probably strictly worse than the prior algorithm in asymptotic efficiency.

Integer linear programming

Finally, it is possible to encode your problem directly as an instance of ILP. I suggest you introduce zero-or-one variables $X_1,\dots,X_n$, with the intent that $X_i=1$ means input vector $v_i$ is included in the combination. Also, define $w = \sum_i X_i v_i$, and introduce zero-or-one variables $Y_{j,0},Y_{j,1},Y_{j,x},Y_{j,2x}$ for $j=1,\dots,d$, with intended meaning as follows:

  • $Y_{j,0}=1$ means that $w_j$ is zero.

  • $Y_{j,1}=1$ means that $w_j$ is not divisible by $x$.

  • $Y_{j,x}=1$ means that $w_j$ is $x$.

  • $Y_{j,2x}=1$ means that $w_j$ is a multiple of $x$ that is strictly larger than $x$ (i.e., $2x$ or $3x$ or ...).

I'll show how to enforce consistency of these variables in a moment using linear inequalities. Once we've done that, all that remains is to require that $X_1 +\dots + X_n=m$ (a combination contains exactly $m$ of the input vectors) and $Y_{1,x}+\dots+Y_{d,x}=m$ (exactly $m$ of the coordinates sum to $x$) and then test whether the entire system of inequalities is feasible, and if so, report all solutions. That can be done using an off-the-shelf ILP solver.

To enforce the consistency of the $X$'s and $Y$'s, we add the following linear inequalities:

  • $Y_{j,0}+Y_{j,1}+Y_{j,x}+Y_{j,2x}=1$ for each $j$ (exactly one of those four cases must be true).

  • $X_i \le 1-Y_{j,0}$ for each $i,j$ such that $v_{i,j}>0$ (something that sums to zero can't have any nonzero terms in the sum).

  • $\sum_{v_{i,j}>0} X_i \ge 1-Y_{j,0}$ for each $j$ (if it doesn't sum to zero, at least one of the terms in the sum is nonzero).

  • $\sum_{v_{i,j}=1} X_i \ge Y_{j,1}$ for each $j$ (something that sums to a non-multiple of $x$ must have at least one term that is a $1$).

  • $X_i \le Y_{j,1}$ for each $i,j$ such that $v_{i,j}=1$ (if the sum has a term that is a $1$, then it sums to a non-multiple of $x$, since $x>n$).

  • $\sum_{v_{i,j}=x} X_i \ge Y_{j,x}$ (anything that sums to $x$ must have at least one term that is an $x$).

  • $\sum_{v_{i,j}=1} X_i \le 1-Y_{j,x}$ (anything that sums to $x$ cannot have any terms that are a $1$).

  • $\sum_{v_{i,j}=x} X_i \ge 2Y_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ must have at least two terms that are an $x$).

  • $\sum_{v_{i,j}=1} X_i \le 1-Y_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ cannot have any terms that are a $1$).

Hardness

Your problem is NP-hard. Consider the special case of your problem where all entries are in $\{0,x\}$ (no input vector contains a $1$), where $m=d$, and where there are at least $m$ copies of the all-zeros vector in the input list. This special case is equivalent to exact cover, which is NP-hard. If a special case of your problem is NP-hard, then your problem is certainly NP-hard. So, we shouldn't expect an efficient algorithm for your problem. See What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, and Dealing with intractability: NP-complete problems for some reference material on those subjects, or grab a good algorithms textbook.

$\endgroup$
  • $\begingroup$ Sorry, I should've been more clear - entries could be only from set of {0,1 or x} - x=10 in my example. No other values are allowed in arrays. Does it change NP-completeness of this problem? $\endgroup$ – Akim Akimov Dec 14 '16 at 23:25
  • $\begingroup$ @AkimAkimov, that does change the problem. See revised answer. Yes, it is still NP-hard. $\endgroup$ – D.W. Dec 15 '16 at 0:02

Your Answer

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

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