Question Since the 3-Dimensional Matching Problem is NP-complete, it is natural to expect that the corresponding 4-Dimensional Matching Problem is at least as hard. Let us define 4-Dimensional Matching as follows. Given sets W, X, Y, and Z, each of size n, and a collection C of ordered 4- tuples of the form (wt, Xj, yk, zt), do there exist n 4-tuples from C so that no two have an element in common? Prove that 4-Dimensional Matching is NP-complete

WNVF4C The Asker · Computer Science

Transcribed Image Text: Since the 3-Dimensional Matching Problem is NP-complete, it is natural to expect that the corresponding 4-Dimensional Matching Problem is at least as hard. Let us define 4-Dimensional Matching as follows. Given sets W, X, Y, and Z, each of size n, and a collection C of ordered 4- tuples of the form (wt, Xj, yk, zt), do there exist n 4-tuples from C so that no two have an element in common? Prove that 4-Dimensional Matching is NP-complete
More
Transcribed Image Text: Since the 3-Dimensional Matching Problem is NP-complete, it is natural to expect that the corresponding 4-Dimensional Matching Problem is at least as hard. Let us define 4-Dimensional Matching as follows. Given sets W, X, Y, and Z, each of size n, and a collection C of ordered 4- tuples of the form (wt, Xj, yk, zt), do there exist n 4-tuples from C so that no two have an element in common? Prove that 4-Dimensional Matching is NP-complete
Community Answer
DW27WK

4-Dimensional Matching is in NP, since we can check in O(n) time, using an n times 4 array initialized to all 0, that a given set of n 4-tuples is disjoint. We now show that 3-Dimensional Matching can be reduced to 4-Dimensional Matching in polynomial time. So consider an instance of 3-Dimensional Matching, with sets X, Y, and Z of size n each, and a collection C of ordered triples. We define an instance of 4-Dimensional Matching as follows. We have sets W, X, Y, and Z, each of size n, and a collection C' of 4-tuples defined so that for every (x_j, y_k, z_l) in C, and every i between 1 and n, there is ... See the full answer