【三维匹配问题】
给定三个不相交的集合X、Y、Z，三个集合的大小都为n。给定一个三元组集合T⊆X×Y×ZT \subseteq X \times Y \times ZT⊆X×Y×Z，集合T的大小为m。
问：T中是否存在一个大小为n的子集T’，这个子集恰好包含X,Y,Z每个元素一次。
三维匹配问题其实是集合覆盖和集合包装问题的特例。
三维匹配问题是NP完全的
首先，很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n，且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的，可以通过3-SAT≤p\leq_p≤p三维匹配证明。
【3-SAT≤p\leq_p≤p三维匹配证明】
