三維匹配問題

三維匹配問題（3DM）是六個經典NP完全問題之一，是經典的「婚姻問題」的推廣，「婚姻問題」的提法是：有幾個未婚男子和幾個未婚女子以及一張列出雙方都表示願意結合在一起的一對對男子和女子的表格，問是否能安排幾對婚姻使得每個人都與自己願意接受的配偶結婚並且不出現重婚？

在三維匹配問題中，可以用集合$W$，$X$和$Y$對應於「三個」不同的性別，$M$屬於$W*X*Y$。用集合$M$中的每一個三元組對應一對這三個成員都能接受的「三方婚姻」。普通的婚姻問題可以在多項式時間內解決，而3DM是NP完全的。