此条目需要精通或熟悉计算机科学、数学的编者参与及协助编辑。 (2021年9月22日) 请邀请适合的人士改善本条目。更多的细节与详情请参见讨论页。 另见其他需要计算机科学专家关注的页面。 |
此条目没有列出任何参考或来源。 (2012年11月2日) 维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而被移除。 |
三维匹配问题(3DM)是六个经典NP完全问题之一,是经典的“婚姻问题”的推广,“婚姻问题”的提法是:有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格,问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚?
在三维匹配问题中,可以用集合,和对应于“三个”不同的性别,属于。用集合中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决,而3DM是NP完全的。