三维匹配问题是NP完全的

【三维匹配问题】 给定三个不相交的集合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​三维匹配证明】