三维匹配问题 - 维基百科，自由的百科全书

此條目需要精通或熟悉计算机科学、数学的编者参与及协助编辑。 (2021年9月22日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。 另見其他需要计算机科学專家關注的頁面。

此條目没有列出任何参考或来源。 (2012年11月2日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

三维匹配问题（3DM）是六个经典NP完全问题之一，是经典的“婚姻问题”的推广，“婚姻问题”的提法是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？

在三维匹配问题中，可以用集合${\displaystyle W}$，${\displaystyle X}$和${\displaystyle Y}$对应于“三个”不同的性别，${\displaystyle M}$属于${\displaystyle W*X*Y}$。用集合${\displaystyle M}$中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决，而3DM是NP完全的。