patternMinor
What is the complexity class of this variant of Subset sum?
Viewed 0 times
thisthevariantwhatsumsubsetclasscomplexity
Problem
Let's represent Subset Sum problem with binary arrays instead of numbers.
Example: given two-dimensional array
is there set of one-dimensional arrays, sum of which is equal to
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
then what complexity class such problems belong to? In what papers it was studied?
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?
Solution
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
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
Context
StackExchange Computer Science Q#89701, answer score: 3
Revisions (0)
No revisions yet.