HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisthevariantwhatsumsubsetclasscomplexity

Problem

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?

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

Context

StackExchange Computer Science Q#89701, answer score: 3

Revisions (0)

No revisions yet.