问题是NP难的。（因此，您不应期望使用多项式时间算法来解决此问题。但是，仍然存在（非多项式时间）算法要比蛮力略好一些。）NP硬度证明的思想是：如果我们能够解决这个问题，那么我们就可以解决一般图中的集团问题。（最大爬坡问题是在图中找到最大的成对连接的顶点集。）

具体来说，给定具有 n 个顶点的任何图，让我们形成矩阵A，其条目a[i][j]如下：

• a[i][j] = 1对于i == j（对角线条目）
• a[i][j] = 0如果图（和i≠j）中存在边（i，j ）
• a[i][j] = -n-1如果边缘（i，j）在图中 不 存在。

现在假设我们解决了删除一些行和列（或等效地， 保留 一些行和列）的问题，从而使矩阵中的条目之和最大化。然后，答案给出了图中的最大提示：

1. 索赔 ：在任何最佳解决方案中，没有保留行i和列j，其中图表中不存在边（i，j）。证明：由于a[i][j] = -n-1所有正条目的和最多为和n，所以选择（i，j）将得出负数。（请注意，删除 所有 行和列将得出更好的总和，为0。）

2. 索赔 ：在（某些）最优解中，保留的行和列的集合相同。这是因为从任何最佳解决方案开始，我们可以简单地删除所有未保留i其列的行，i反之亦然。请注意，由于唯一的正项是对角项，因此我们不会减少总和（根据先前的声明，我们也不会增加总和）。

所有这些都意味着，如果图具有最大的集团规模k，那么我们的矩阵问题将具有sum的解，k反之亦然。因此，如果我们能够在多项式时间内解决初始问题，那么团簇问题也将在多项式时间内解决。这证明了最初的问题是NP-
hard
。（实际上，很容易看到初始问题的决策版本-
是否有一种方法可以删除一些行和列，使总和至少为k-在NP中，因此初始问题的（决策版本）为实际上是NP完整的。）