4_partition_hardness_proof (1027B)
1 # 4_partition_hardness_proof 2 3 Proof in http://courses.csail.mit.edu/6.890/fall14/6046-L16.pdf 4 reduction from [3_dimensional_matching] 5 - write numbers in a large [basis] 6 - the i-th element xi is coded as (10, i, 0, 0, 1) 7 and many copies of (11, i, 0, 0, 1) 8 - the j-th element yj is coded as (10, 0, j, 0, 2) 9 and many copies of (11, 0, j, 0, 2) 10 - the k-th element zk is coded as (10, 0, 0, k, 4) 11 and many copies of ( 8, 0, 0, k, 4) 12 - a triple (xi, yj, zk) is coded as 13 (10, -i, -j, -k, 8) 14 - the target to reach for each 4-tuple is: (40, 0, 0, 0, 15) 15 - the basis is large so, starting from least significant digits: 16 - use one value from each type 17 - match each triple with a matching zk 18 - match each triple with a matching yj 19 - match each triple with a matching xi 20 - match a triple with the used elements, or match a triple with unused elements 21 - so each real element (labeled 10) of the xi yj zk must appear in exactly one triple 22 23 Up: [4_partition]