Skip to main content
Tweeted twitter.com/StackCompSci/status/977373344654876672
edited tags
Link
DSblizzard
  • 484
  • 1
  • 4
  • 10
Source Link
DSblizzard
  • 484
  • 1
  • 4
  • 10

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

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?