此條目需要精通或熟悉電腦科學、數學的編者參與及協助編輯。 (2021年9月22日) 請邀請適合的人士改善本條目。更多的細節與詳情請參見討論頁。 另見其他需要電腦科學專家關注的頁面。 |
此條目沒有列出任何參考或來源。 (2012年11月2日) 維基百科所有的內容都應該可供查證。請協助補充可靠來源以改善這篇條目。無法查證的內容可能會因為異議提出而被移除。 |
三維匹配問題(3DM)是六個經典NP完全問題之一,是經典的「婚姻問題」的推廣,「婚姻問題」的提法是:有幾個未婚男子和幾個未婚女子以及一張列出雙方都表示願意結合在一起的一對對男子和女子的表格,問是否能安排幾對婚姻使得每個人都與自己願意接受的配偶結婚並且不出現重婚?
在三維匹配問題中,可以用集合,和對應於「三個」不同的性別,屬於。用集合中的每一個三元組對應一對這三個成員都能接受的「三方婚姻」。普通的婚姻問題可以在多項式時間內解決,而3DM是NP完全的。