What is the complexity class of this variant of Subset sum?

Question

Let's represent Subset Sum problem with binary arrays instead of numbers. Example: given two-dimensional array

[1, 0, 0] (4)
[1, 0, 1] (5)
[0, 0, 1] (1)

is there set of one-dimensional arrays, sum of which is equal to

[1, 0, 0, 1] (9)

In this problem sum of bits in each position can have carry-over. If carry-overs are forbidden (bit positions are independent) and we ask instead: are there arrays which sums to

[2, 0, 1]

then what complexity class such problems belong to? In what papers it was studied?

Answer 1

This is NP-hard. The associated decision problem is NP-complete.

There are various ways to prove that. For instance, there's a straightforward reduction from exact cover; let the target array be all-ones, and then you have an instance of the exact cover problem, which is NP-hard.

Your problem is an instance of multi-dimensional subset sum (or multi-dimensional knapsack), for which you can find algorithms and approximation algorithms in the literature.

Related: https://cstheory.stackexchange.com/q/19976/5038, How to find subset of vectors whose sum has certain characteristics, https://cstheory.stackexchange.com/q/21865/5038, https://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints