一道野生的 NP-Complete 问题解法（有误）

本文初次发布时间为 2021 年 4 月 25 日。 最后更新时间为 2025 年 6 月 11 日，在「第 0 节」更新了回顾，并在标题后方增加（有误）标识。

0. 回顾

本文所列证明存在明显错误。

• 第一，题目的问题可以轻易被二分图最大匹配问题的解决方案解决，而这是一个多项式时间可以解决的问题。
• 第二，在规约过程中，「有至少 $q$ 个顾客需要满足，也就是所有顾客都要被满足」一句忽略了 3D-Matching 到题设「搭配偏好」的构建，以致于整个规约将其视为不证自明的并忽略了这一点。

感谢 Telegram 网友「⛩️-11」 提出的质疑推动了本文的更新。

1. 题目

商店有 $a$ 条裤子和 $b$ 件衬衫，每件衣服唯一。$k$ 个顾客各自有不同的裤子衬衫搭配偏好。

存不存在多项式时间复杂度的解法来判定至少 $M$ 个顾客能够被满足自己的偏好需求？存在的话给出解法；如果是 NP-Complete 的话给出经典 NPC 问题到这个问题的归约。

2. 答

不存在，且此问题是 NP-Complete。

归约的完全性由经典 NPC 问题 3D-Matching 给出。

3. 背景

3.1. 3D-Matching 是什么？

对于三个集合大小相同的集合 $X, Y, Z (|X|=|Y|=|Z|=q )$，集合笛卡尔积运算结果的子集记为 $M ⊆ X×Y×Z$。要找到一个大小为 $q$ 的子集 $M’$ ，使得它其中的任意两个元素 $(x_1, y_1, z_1)$ 和 $(x_2, y_2, z_2)$ 在三个维度上都不相等，也就是说 $x_1 ≠ x_2$ ，同时 $y_1 ≠ y_2$ ，同时 $z_1 ≠ z_2$。这样的子集 $M’$ 就是我们要找的 3D-Matching ，而判定它是否存在是一个 NP-Complete 问题，由 Richard Karp 在 1972 年证明。

3.2. 归约是什么？

归约的本质是把一个已经证明为 NPC 的问题的任意情况归约到我们要证的问题的特殊情况上。如果归约有效，说明这个要证的问题的难解性不低于已证 NPC 问题，从而证明这是一个 NPC 问题。

针对这个题目，就是我们想试着从 3D-Matching 的任一情况归约到一个题设的特殊情况。所以，我们可以对于要证明的问题做一些条件限制，使它更特殊一点。

4. 限制条件

第一，令裤子的集合 $A$ ，衬衫的集合 $B$ ，顾客的集合 $K$ ，他们三者数量相等，记为 $n$ 。即 $a=b=k:=n$ ；

第二，令题目要求的 $M$ 至少为 $n$，也就是说判定所有 $n$ 个顾客能够被满足自己的偏好需求。

这个题设相对于原问题来说条件更加严格，和原来的问题性质是一样的。这是因为 a, b, k, M 在原问题里是没有限制的，原问题相当于指代了 M=1,2,...,n 的这一类问题。而我们证明的是其中的一个子问题是 NP-Complete 的。即便 M=1,2,...,n-1 都有多项式时间内的解法，只要原问题有一个子问题是 NPC 的，就可以说这个问题是 NPC 的。

5. 归约过程

对于任意三个大小相等且为 $q$ 的集合 $X, Y, Z$ ，若存在这样一个解的集合 $M’$ ，这个集合一共有 $q$ 个三元组满足 3D-Matching。

我们可以限制出一个题设的特殊情况来求出等价的解。令 $A=X , B=Y , K=Z$ ，它们大小相等， $a=b=k=q$ 。我们有至少 $q$ 个顾客需要满足，也就是所有顾客都要被满足。题设问题得出来的解中，每个顾客都会有一个衬衫与裤子搭配的偏好被满足，我们从 $A$ 中挑出这个裤子，$B$ 中挑出这个衬衫，和这个顾客组成一个三元组。

简单说明一下，这个三元组里的顾客不会是其他人，而衬衫和裤子也不会被其他人买走。也就因此完成了归约。

6. 后续

以上说明并不严密。如果要严格证明，还需要证明以下几件事。

第一，题设问题是 NP ，也就是它的解可以在多项式时间复杂度里被判定为正确；

第二，这个归约在多项式时间内可以完成；

第三，任意一个 3D-Matching 的解都对应着一个题设问题的解；

第四，任意一个在限制条件起作用的题设问题下获得的解都对应一个 3D-Matching 的解。