3_dimensional_matching_hardness_proof (742B)
1 # 3 dimensional matching hardness proof 2 3 Shown NP-hard [nptime] in [garey_johnson], reduction from [3sat]: 4 - for each variable do a "flower" gadget 5 - http://courses.csail.mit.edu/6.890/fall14/6046-L16.pdf 6 - at the center put elements of X and Y that are local to each variable, alternatively 7 - at the extremities put elements of Z that correspond either to x or barx 8 - for each clause there are two elements of X and Y local to that clause to impose that it is covered, and there are 3 ways to cover that use each "allowed" literal 9 - some additional things: for every excess variable occurrences, a gadget with two specific elements of X and Y and all possible Z to cover exactly one unused variable 10 11 Up: [3_dimensional_matching]