# 3D Matching

2D matching

Input: 2 sets $X,Y$ of size $n$ and a family of edges $E⊂X×Y$Output: is there a perfect matching ($n$ edges that cover $X,Y$)?- This is testing if a bipartite graph has a perfect matching

3D matching

Input: 3 sets $X,Y,Z$ of size $n$ and a family of hyperedges $E⊂X×Y×Z$Output: is there a perfect matching ($n$ hyperedges that cover $X,Y$ and $Z$)? (each $x_{i}$ (and each $y_{j}$ , and each $z_{k}$) is in a unique hyperedge)NP