reduction_3dm_subset_sum (360B)
1 # Reduction 3dm subset sum 2 3 reduction from [3_dimensional_matching] to [subset_sum]: 4 - for n = |X| + |Y| + |Z| 5 - take a base K which is sufficiently big to avoid [carry] 6 - reach (1...1) n times 7 - every triple gives you a number with exactly 3 bits carrying a 1 corresponding to its elements 8 9 Shows that [subset_sum] is [NP_hard] 10 11 Up: [reduction], [subset_sum]