我有以下问题：给定一组男性和一组女性，任意两个人之间的等级等于0或1.选择一部分人，使得：
我的问题是：为了显示这个问题的完整性，我知道可以使用clique问题减少...有没有人能提供一个如何进行这种减少的例子？我是否需要减少FROM或TO clique问题？非常感谢
要回答你的问题，你需要从clique问题减少到你目前正在处理的问题，因为clique是一个已知的NP完全问题。
至于你的转型过程的提示（从已知的Clique问题到你的排名问题），一个好的方法来考虑这个问题，你将如何减少你的问题集团的情景。我假设1表示“关联人”，0表示问题中“不喜欢的人”。
将每个人作为图G中的顶点（在集团问题中假设给定图）。为区分男性和女性，我们将男性组标记为A1，A2，A3 ...... Am，女性组标记为B1，B2，B3 ...... Bf。现在我们可以为他们之间排名为1的每一对人绘制边缘（喜欢的人）。假设图完成后形成N（N> = 1）个派系。
现在，我们删除每个集团中的顶点，使得集团具有不等数量的As和Bs（以在两个性别中提供相同数量的顶点）。现在，最大的数字集团是你将要寻找的。
这种转换应该在多项式时间内完成，因为我们正在做的是纯粹重构我们的clique图并标记它们（并删除它们）。执行这种转换将是O（V + E）。
之后，如果您想证明您的问题是NP完全的，那么您将被要求证明答案在问题答案和集团问题答案之间有效。
我不会为你写出实际的证据，但我希望以下关于如何构建证据的大纲有助于回答你的问题。
证明问题是使用简化完成NP的第一步是实际证明问题出在NP中。也就是说，可以在多项式时间内验证问题。
你是怎样做的？您的问题可以转变为决策问题（例如，是/否问题）这个决策问题是否可以被认证？您的决策问题是否有答案/解决方案？您能否验证决策问题的证书是否可以在多项式时间内完成？如果是，那么你已经证明你的问题在NP中。
现在您已经知道问题出在NP中，您可以使用简化来证明问题是NP完全的或NP难的。 （如果问题出现在NP中，那么在进行还原步骤时绝对没有用，因为如果不在NP中，问题就不能完成NP。）
为了减少，你应该将clique问题转化为你的问题。你是怎样做的？好吧，想想集团问题的哪些要素可以转化为问题的要素。你的问题中有男性/女性，但是在集团问题中有节点/顶点。在您的问题中有连接等于0（unliked）或1（喜欢），但是clique问题中有加权（或未加权边缘）。您正试图找到它们之间具有最多喜欢数量的人的子集，但是在集团问题中，您正在最大化集团中的顶点数。在大多数情况下，它几乎看起来像是一对一的转变。问题的棘手部分是必须有偶数的男性和女性。为此，您需要更具创造性，并找到改变集团问题的方法。
一旦你将问题从集团转变为你的问题，你就可以简单地证明集团问题的答案是你问题的答案，反之亦然。
这是证明问题是NP难的结构。最难的部分是转型过程。然而，重点是，如果你深入思考，可以操纵集团问题，以便它转变为你的问题。
希望有所帮助！