团

在计算机科学领域，寻找图中的团（一组相邻的顶点，也称为完全子图）是一项计算挑战。根据要收集的团和关于它们的信息的不同，它有许多不同的表述。寻找最大团（拥有最多顶点的团）、确定加权图中的最大权重团、编译所有极大团（无法再扩大的团）的列表以及确定确定图是否包含大于特定大小的团的决策问题，都是团问题的常见表述示例。

以下场景描述了团问题在现实生活中如何体现。考虑一个社交网络，其中顶点是人，边是他们之间的连接。那么，一个团表示一群彼此都认识的人，而检测团的方法可以用来识别这些社交网络。团问题在计算化学、生物信息学和社交网络中有广泛的应用。

大多数团问题的变种都具有挑战性。Karp 提出的 21 个 NP 完全问题之一的团选择问题是 NP 完全的。寻找最大的团是一个难以估计且固定参数不可解的任务。此外，由于存在具有指数级数量最大团的图，列出所有这些团可能需要指数级的时间。因此，围绕团问题的很大一部分理论集中在寻找允许更有效算法的特定图类型，或者确定不同计算模型中一般问题的计算复杂度。

可以通过系统地检查所有子集来找到最大团，但网络中几十个以上的顶点使得这种蛮力搜索不切实际。虽然这个问题没有多项式时间解，但存在比蛮力搜索更有效的替代方法。例如，Bron-Kerbosch 方法可用于在多项式时间内为每个团或在最坏情况下最优时间内列出所有最大团。

背景与应用

即使在“团”这个名字出现之前，数学家们就已经研究过完整的子图。例如，在 Erds & Szekeres (1935) 的图论重述的 Ramsey 理论中，完整子图在数学文献中首次出现。然而，“团”这个名字以及算法列出团的问题源于社会科学，在那里，社交团（即彼此都认识的人群）被建模为完整的子图。Luce 和 Perry (1949) 将社会科学语言引入图论，并使用图来表示社交网络。

他们最初将完整的子图称为“团”。受社会学应用的启发，Harary & Ross (1957) 开发了第一个解决团问题的算法。社会科学家还识别出其他类型的团和最大团，作为网络参与者或行为者（都具有某种类型的连接关系）的“内聚子集”。通过构建一个无向图，其边反映了社交网络中成对连接的行为者，然后将团问题的算法应用于该图，可以发现许多这些广义的团概念。

自 Harary 和 Ross 的方法以来，许多人已经开发了针对团问题不同迭代的方法。研究人员从最坏情况分析的角度开始研究这些算法，这始于 20 世纪 70 年代。关于极大团问题最坏情况复杂度的开创性研究，请参见 Tarjan & Trojanowski (1977)。研究人员开始应用 NP-完全性的概念以及相关的难解性结果，为 20 世纪 70 年代开始的团问题明显的复杂性提供数学依据，这要归功于 Cook (1971) 和 Karp (1972) 的工作。一系列发表于 20 世纪 90 年代的开创性著作，始于 Feige 等人 (1991) 的研究，表明（假设 P ≠ NP）无法高效地近似解决该问题。

化学领域使用团查找算法来预测分子对接、化学过程的结合位点以及寻找适合目标结构的化合物。它们还可以用于识别其他化合物之间的相似结构。在这些应用中，创建一个图，其中每个顶点表示两个不同分子中一对匹配的原子。如果两个顶点代表的匹配兼容，则它们之间会有一条边连接。兼容意味着两个分子内的原子间距在一定容差范围内大致相似。

在该图中，团是原子匹配的集合，其中每个匹配都与其他匹配兼容。将确定两个图之间最大共享诱导子图的问题转化为确定其乘积中的最大团的问题，这是该方法的一种特定形式，通过使用图的模乘积。

在自动生成测试模式时，查找团可以帮助限制测试集的大小。在生物信息学中，已使用团查找算法来识别具有强相互作用的蛋白质簇 [9]、预测蛋白质结构和推断进化树。列出依赖图中的团是研究某些随机过程中的关键步骤。在数学中，Lagarias & Shor (1992) 通过在相关网络上使用团查找技术来发现反例，从而否定了 Keller 关于超立方体面对面平铺的假设。

定义

一个有限的顶点集合和一组无序的顶点对（称为边）构成一个无向图。按照惯例，在算法分析中，边数用 m 表示，图中的顶点数用 n 表示。在图 G 中，团是 G 的一个完整子图。换句话说，它是顶点的子集 K，其中 K 中的每对顶点都充当 G 中边的起点和终点。

无法将任何其他顶点添加到最大团中。极大团中必须有一个顶点 w，它不与所有不在团中的顶点 v 相邻，从而阻止 v 加入该团。一个拥有最多顶点的团称为极大团。G 中最大团的顶点数称为团数 (G)。

对几个密切相关的团查找问题进行了研究

• 在最大团问题中，输入是一个无向图，输出是图的最大团。如果有多个最大团，可以随机选择其中一个。
• 加权最大团问题会产生一个无向图（其顶点上有权重，或较少见的边上有权重）的最大总权重。所有权重相等的特殊情况是极大团问题。除了优化权重和的问题外，还研究了其他更具挑战性的双标准优化问题。
• 在最大团列出问题中，输入是一个无向图，输出是其所有极大团的列表。由于最大团必须包含在所有极大团中，因此解决极大团列出问题的方法可以用作解决最大团问题的子程序。
• 一个无向图和一个整数 k 是 k-团问题的输入。如果存在 k-团，则输出是具有 k 个顶点的团；否则，返回一个特殊值表示不存在 k-团。此问题某些变种的输出应该是所有大小为 k 的团的列表。
• 无向图和整数 k 是团选择问题的输入。如果图包含一个 k-团，则输出为真布尔值；否则为假。
• 前四个问题在现实场景中都非常重要。团选择问题之所以这样表述，是为了将 NP-完全性的概念应用于团查找问题，尽管它没有实际用途。

G 中的一个团是 G 的补图中一个独立集，反之亦然，这使得团问题和独立集问题相互补充。因此，许多计算结果可以应用于每个问题，并取得相似的成功，而其他研究必须明确区分这两个问题。然而，当应用于某些图族时，这两个问题具有不同的特征。例如，虽然独立集问题对于平面图来说仍然是 NP-难的，但团问题可以在多项式时间内解决。

算法

一个不属于更大团的团称为极大团，也称为包含极大团。因此，最大团包含所有团。可能存在最小的极大团。一个图可能有一个大的非极大团，包含许多顶点，以及一个更小的、大小为 2 的极大团。虽然最大（或最大）团不可避免地是极大的，但反之则不成立。在“充分覆盖图”（其中每个极大独立集都是最大）的补图中，每个极大团都是最大的。然而，其他图包含的极大团不是最大的。

一个简单的贪心方法可以找到一个单一的最大团。通过遍历图中的剩余顶点，从一个任意的团（例如，任何单个顶点甚至整个集合）开始，可以增长当前团。对于循环检查的每个顶点 v，如果它与团中已有的每个顶点都相邻，则将 v 添加到团中；否则，拒绝 v。此算法是线性进展的。由于找到极大团的简单性及其可能的小尺寸，发现最大团或其他大团的更具挑战性的算法问题受到了更多的关注。

然而，一些并行算法研究已经研究了获得最大团。对于多项式时间函数类，已证明找到字典序第一的最大团（由上述方法发现）的问题是完整的。这一发现表明，该问题不太可能在并行复杂度类 NC 中解决。

具有集合大小的团

可以使用蛮力方法来确定图 G 是否具有 k-顶点团并找到任何这样的团。此算法会检查具有 k 个顶点的每个子图，并确定是否存在一个团。大 O 记法表示这需要 O(nk k2) 的时间。这是因为有 O(nk) 个子图要检查，每个子图有 O(k2) 条边，这些边的存在性必须在 G 中得到验证。因此，当 k 是一个固定的常数时，该问题可以在多项式时间内解决。然而，当 k 是问题的一个可变输入而不是一个固定值时，时间是指数级的。

找到图中的一个三角形，或者更准确地说，确定图是否不含三角形，是团问题最基本但并非平凡的例子。在具有 m 条边的图 G 中，最多可能有 (m3/2) 个三角形（使用大 theta 符号表示此约束是严格的）。此公式的最坏情况发生在 G 本身是一个团时。因此，在最坏情况下（使用大 omega 符号），列出所有三角形的算法至少需要 (m3/2) 时间，并且存在符合此时间限制的已知算法。

例如，Chiba & Nishizeki (1985) 提供了一种方法，该方法迭代列表中的每个顶点 v，查找包含 v 且不包含列表中任何先前顶点的三角形。按照示例，顶点按度从大到小排序。该方法通过标记所有邻居，然后遍历所有邻居的边，为具有两个标记端点的每条边生成一个三角形，然后清除标记，并从图中删除 v 来完成此操作。

如作者所示，此方法的运行时间为 O(m a(G))，其中 m 是边数乘以图的林度（记为 a(G)）。由于林度最多为 O(m1/2)，因此该方法需要 O(m3/2) 时间才能完成。对于林度恒定的图（例如，平面图，或通常来自任何非平凡的子图闭合图族），该方法只需要 O(m) 时间，这是理想的，因为它与输入大小呈线性关系。如果只需要一个三角形或保证图不含三角形，则可能存在更快的技术。根据 Itai 和 Rodeh (1978) 的说法，只有当一个图的邻接矩阵与其邻接矩阵的平方在同一单元格中都有非零项时，才能在该图上找到三角形。使用快速矩阵乘法技术，可以在 O(n2.376) 时间内找到三角形。Alon、Yuster 和 Zwick (1994) 使用快速矩阵乘法将三角形查找算法的效率从 O(m3/2) 提高到 O(m1.41)。这些基于快速矩阵乘法的技术也已应用于识别更大 k 值的 k-团问题。

所有最大团列表

根据 Moon & Moser (1965) 的说法，每个 n-顶点图最多包含 3n/3 个最大团。Bron-Kerbosch 算法是一种递归回溯方法，由 Bron & Kerbosch 于 1973 年开发，可以列出它们。过程的主要递归子程序有三个参数：一个部分构建的（非极大）团、一组可能添加到该团的候选顶点，以及一组不应添加的顶点（因为这样做会产生一个已找到的团）。

该过程对每个候选顶点进行递归调用，一次将它们添加到部分团中。尝试每个顶点后，将这些顶点中的每一个添加到不应再次添加的列表中。可以证明，此方法的一个变种在最坏情况下的运行时间为 O(3n/3)，这与必须列出的团的潜在数量相对应。因此，它为列出所有最大团的问题提供了一个最坏情况最优的解决方案。此外，人们普遍观察到，Bron-Kerbosch 算法的实际运行速度比其竞争对手更快。

然而，当团的数量远少于其最坏情况时，可能更倾向于选择其他方法。Tsukiyama 等人 (1977) 证明，在多项式时间内列出图中的所有最大团也是可能的。像他们的算法这样的算法被称为输出敏感算法，如果执行时间受输出大小的影响。他们算法的基础是两个观察结果，即将给定图 G 的最大团与通过删除 G 中的任意顶点 v 而创建的图 G v 的极大团联系起来。

• 对于 G v 的任何极大团 K，K 要么在 G 中保持其极大团，要么 K v 在 G 中形成一个最大团。因此，G 中的最大团数量与 G v 中的数量大致相同。
• G 中不包含 v 的每个极大团都是 G v 中的一个极大团，而 G 中包含 v 的每个极大团都可以从 G v 中的一个极大团 K 通过包含 v 并删除 K 中 v 的非邻居来创建。

借助这些发现，他们可以通过一个递归过程创建 G 中的所有最大团，该过程随机选择一个顶点 (v)，然后为 G v 中的每个极大团 (K) 创建 K 和通过将 v 添加到 K 并删除 v 的非邻居而形成的团。他们只输出 G 中的一个团，当其父节点在 G v 中是所有可行父团中字典序最大的时，因为 G 中的某些团可以通过这种方式从多个 G v 的父团形成。这可以防止重复团的创建。

基于这种方法，他们证明了 G 中的所有最大团可以在每个团 O(mn) 的时间内创建，其中 m 是 G 中的边数，n 是顶点数。Chiba & Nishizeki (1985) 将其改进为每个团 O(ma)，其中 an 是给定图的林度。Makino & Uno (2004) 提出了一种基于快速矩阵乘法的替代输出敏感技术。Johnson 和 Yannakakis (1988) 证明了所有最大团都可以按字典序排列，并且每个团都有多项式延迟。该方法的有效性取决于排序的选择，因为除非 P = NP，否则对于此顺序的逆序不存在多项式延迟解。

基于这一发现，对于团数量在多项式时间内有界（相对于输入大小）的图族，可以列出所有最大团。例如，弦图、完全图、无三角形图、区间图、毒性有限的图以及平面图。特别是，平面图具有 O(n) 个团，可以在线性时间内列出，其最大大小为常数。对于任何稀疏图族（作为子图闭合），情况也是如此（边数最多等于顶点数）。

查找任何给定图中的最大团

可以使用上述技术之一来列出网络中的所有极大团，然后返回最大的一个，从而在 O(3n/3) = O(1.4422n) 的时间内确定任何给定 n-顶点图的最大团或团数。尽管如此，对于这个团问题版本，仍然存在更好的最坏情况时间限制。Tarjan 和 Trojanowski 的方法以 O(2n/3) = O(1.2599n) 的时间解决了这个问题。与 Bron-Kerbosch 方法一样，它也使用递归回溯，但当可以证明在此内部找到的团不会是最优的时，它可以跳过一些调用。Jian (1986) 和 Robson (1986) 分别将时间提高到 O(20.304n) = O(1.2346n) 和 O(20.276n) = O(1.2108n)，代价是使用了更多的空间。Robson 的算法使用一种更复杂的案例分析、类似的 backtracking 策略和动态规划技术，预先计算了补图中每个小连通子图的最佳解决方案。通过使用这些不完整的解决方案，可以避免 backtracking 递推。目前最快的算法是 Robson (2001) 开发的该技术的一个修改版本，其运行时间为 O(20.249n) = O(1.1888n)。

此外，还有许多关于启发式算法的研究，这些算法使用技术，如分支定界、局部搜索、贪心算法和约束编程来解决最大团问题，但没有提供最坏情况性能保证。还提出了诸如 DNA 计算和绝热量子计算等非常规技术来识别团。1992-1993 年，DIMACS 赞助了最大团问题的一个实现挑战，该挑战产生了一组现在在线提供的基准图。

某些图类型

如上所述，平面图和其他稀疏图族包含许多有限大小的线性团，可以在线性时间内列出。Kuratowski 定理指出，平面图的任何团最多只能有四个顶点。

它们的团数等于其色数，并且这种等价性在其每个诱导子图中都成立，这被称为完美图。使用基于半定规划的方法，可以在多项式时间内找到完美图的最大团。

完美图的各种子类有独特的团查找方法，因为这种方法很复杂且不是组合式的。Knig 定理允许使用匹配技术在二部图的补图中解决最大团问题。最大团是定义排列网络的排列的最长递减子序列，并且可以使用最长递减子序列问题的既定技术来找到它。另一方面，最长递减子序列问题可以在每种情况下表述为在排列图中找到最大团的问题。[45] Pnueli & Lempel 于 1972 年提供了一种不同的二次时间技术来查找可比图（一个更大的完美图族，其中包含排列图作为特殊情况）中的极大团。通过列出排列图中的顶点，可以识别最大团，并检查该排序中每个顶点的团邻居。

在某些情况下，这些技术也可以用于其他不完美图。圆图中的最大团可以通过对每个邻域运行排列图方法来获得，因为圆图中每个顶点的邻域是一个排列图。同样，单元磁盘图（具有已知几何表示）中的极大团的多项式时间技术是基于将二部图补集的算法应用于顶点对的共享区域。

Karp (1976) 提出了一个算法问题，即在从 Erds-Rényi 模型派生的随机网络中查找极大团，其中每个边以 1/2 的概率出现，独立于其他边。由于这种网络很可能具有对数大小，因此蛮力搜索可以在预期时间 2O(log2n) 内找到随机图中的最大团。这个时间界限几乎是多项式的。即使这样的网络通常具有接近 2 log2n 的团数，基本的贪心算法和更高级的随机近似方法也只能找到大小为 log2n 的团，这只有一半的大小。由于这些图中的极大团数量很可能指数级地增长（以 log2n 为单位），因此列出所有最大团的方法无法在多项式时间内运行。已对“植入团”问题进行了研究，该问题是在随机图上进行的团问题，通过添加大团来增强，许多作者都对此进行了研究。目前尚不知道存在多项式时间方法来找到大小为 o(n)（用小 o 符号表示）的隐藏团，尽管谱方法和半定规划可以找到大小为 (n) 的隐藏团。

近似算法

许多作者已经考虑了近似算法，这些算法试图在多项式时间内找到一个大小尽可能接近最大值的团或独立集，即使它不是极大的。尽管许多这类工作都集中在稀疏网络中的独立集上，但也有关于非稀疏性假设的近似方法的研究。这种场景需要对互补团问题进行更有意义的考虑。

Feige (2004) 提供了一种多项式时间技术，该技术可以发现任何团数为 (n/logkn)（对于任何常数 k）的图中的大小为 ((log n/log log n)2) 的团。通过在团数介于 n/log n 和 n/log3n 之间的给定输入图上使用此算法，切换到 Boppana & Halldórsson (1992) 的另一种算法来处理具有更高团数的图，并在两种算法都失败找到任何东西时选择一个双顶点团，Feige 提供了一种近似算法，该算法找到的团的大小与最大值相比，因子为 O(n(log log n)2/log3n)。尽管此技术的近似比很差，但仍然是最好的。根据下文讨论的近似难度结果，没有近似过程的近似比会显著小于线性。

下限

团选择是一个 NP 完全问题。在其 1972 年的著作《组合问题的约化》中，Richard Karp 证明了它是他提出的最初 21 个问题之一，并且是 NP 完全的。Stephen Cook 关于 NP 完全问题理论的工作也提到了这个问题。由于选择问题的复杂性，寻找极大团是一个 NP-难问题。

通过比较最大团的大小与选择问题中作为输入提供的参数大小，也可以解决决策问题。

从布尔可满足性问题到团选择问题的多项式归约是 Karp 的 NP 完全性证明。它解释了如何将合取范式 (CNF) 布尔方程转换为等价的最大团问题实例。反过来，Cook-Levin 定理证明了可满足性是 NP 完全的。Karp 从给定的 CNF 公式创建一个图，该图包含一个顶点，表示每个对 (v,c)，其中 v 是变量或其否定，c 是包含 v 的公式子句。如果这两个顶点表示不同子句的兼容变量赋值，则它们由一条边连接。换句话说，只要 c d 且 u 和 v 不是彼此的否定，就存在从 (v,c) 到 (u,d) 的边。该图中的 k-顶点团反映了为满足 CNF 公式而为某些变量赋值的相容方法，其中 k 是公式中的子句数。因此，k-顶点团要求公式得到满足。

与蛮力搜索相比，一些 NP 完全问题（例如平面网络中的旅行商问题）可以在输入大小参数 n 的亚线性函数的指数时间内解决。尽管这可能意味着对许多其他常见的 NP 完全问题存在亚指数级界限，但对于任意图中的团问题来说，似乎不太可能实现这种亚指数级时间限制。

电路复杂度

团问题已被用于提供电路复杂度的几个下界，因为它具有计算上的复杂性。如果一个图 G 中存在一个团，那么它在任何超图中也存在，因为一定大小的团是单调图特征。由于这个条件是单调的，一个单调电路必须只使用 AND 和 OR 门来解决固定大小团的团选择问题。然而，可以证明，这些电路的大小是顶点数立方根的指数函数，并且是顶点数和团大小的超多项式函数。即使只允许少数 NOT 门，复杂度仍然是超多项式的。对于具有有限扇入门的团问题的单调电路，其深度至少是团大小的多项式。

决策树复杂度

在最坏情况下，为了确定图是否满足给定属性而必须回答的“顶点 u 和顶点 v 之间是否存在边？”查询的数量，称为（确定性）决策树复杂度。换句话说，它是布尔决策树的最小高度。可能存在 n(n-1)/2 个不同的查询。因此，可以使用最多 n(n-1)/2 个查询来发现任何图属性。对于一个随机或量子算法，准确评估给定图是否满足该属性所需的查询数量（针对最坏情况输入）的预期值，是衡量属性难度的另一种方法。

Aanderaa-Karp-Rosenberg 猜想（声称识别任何非平凡单调图属性的确定性决策树复杂度正好是 n(n-1)/2）适用于包含团的条件，因为它也是单调的。对于任何单调图属性，该猜想仍有待证实。Bollobás (1976) 证明了对于确定性决策树，包含 k-团的属性的决策树复杂度正好是 n(n-1)/2，对于 2 ≤ k ≤ n 的任何 k 都成立。确定性决策树在寻找特定大小的团时也需要巨大的多项式或指数级大小。此外，根据 Aanderaa-Karp-Rosenberg 猜想，非平凡单调函数的随机决策树复杂度为 Ω(n2)。该猜想对于包含 k 团（对于 2 ≤ k ≤ n）已被解决，但尚未得到证实。此属性的随机决策树复杂度已知为 Ω(n2)。量子决策树的最佳已知下界为 Ω(n)，但对于 k ≥ 3 的情况，尚无相应的技术。

固定参数的不可解性

在图中查找 k-团是参数化复杂度理论概念的一个例子，该理论研究了自然出现的小整数参数 k 的问题。如果存在一个算法，其输入大小为 n，并且存在一个函数 f，使得该方法在时间 f(k) nO(1) 内完成，则该问题被认为是固定参数可解的。如果对于任何固定的 k 值，都可以将其解决为多项式时间，并且多项式指数不依赖于 k，则它是固定参数可解的。

查找 k-顶点团的蛮力搜索方法的时间复杂度为 O(nk k2)。此算法不是固定参数可解的，因为 n 的指数取决于 k。快速矩阵乘法可以减少它，但运行时间仍然具有 k 的线性指数。因此，即使现有的团问题算法对于任何固定的 k 具有多项式运行时间，它们也需要超过固定参数可解性。Downey & Fellows (1995) 确定了一个参数化问题集 W 层级，并推测它们没有固定参数可解的方法。他们证明了该层级的第一个级别 W[1] 对于独立集（或等价地，团）是困难的。因此，他们推测团缺乏固定参数可解的方法。此外，这一发现类似于参数化复杂度的 Cook-Levin 定理，因为它构成了支持许多其他问题 W[1] 困难的论证基础。

根据 Chen 等人 (2006) 的说法，除非指数时间假设被推翻，否则在图中查找 k-顶点团无法在 no(k) 时间内完成。这再次表明无法创建固定参数可解的方法。

对于极大团的列出或最大团的查找，不太可能实现固定参数可解性（参数为 k）。然而，在其他情况下，它们可能是复杂的。由于输入图的退化度，这两个问题都被认为是固定参数可解的。

近似难度

弱的结果（已知一段时间）表明，团问题可能难以近似。Garey & Johnson (1978) 指出，团数不可能有真正多项式时间的近似方法，因为它只取很小的整数值，并且计算起来是 NP-难的。

如果近似过于精确，通过将结果四舍五入到整数就可以得到实际的团数。但到了 20 世纪 90 年代初，情况有了更多的了解，当时各种作者开始在极大团的近似和概率可验证证明之间建立联系。利用这些联系证明了最大团问题近似结果的困难性。经过对这些结果的多次更新，人们了解到，除非 P = NP，否则任何多项式时间方法都不能将最大团近似到大于 O (n1) 的因子（对于任何实数 > 0）。

对于像布尔可满足性问题这样的 NP 完全问题，这些不可近似性结果背后的基本思想是创建一个图，该图反映了一个概率可验证证明系统。证明被建模为概率可验证证明系统中一系列位。如果可满足性问题实例是可满足的，则它应该有一个有效的证明。在对可满足性问题输入执行多项式时间计算后，算法会检查证明，重点关注证明字符串的有限数量的随机选择点。

在不查看其余位数的情况下，检查程序将根据在该位样本处获得的值接受或拒绝证明。不允许误报；总是接受有效证明。然而，错误的证据有时可能会被无意中接受。检查程序接受错误证据的可能性必须很小。

为了将这种概率可验证证明系统转换为团问题，必须创建一个图，该图包含表示证明检查程序的可接受运行的每个潜在情况的顶点。换句话说，一个顶点由正在检查的潜在随机位置集以及这些位置上将使证明检查程序接受证据的位值指定。可以使用在每个检查位置具有 0 或 1，在每个空闲位置具有通配符字符的部分单词来表示它。如果两个接受的运行在它们共同检查的每个位置上看到相同的位值，则这两个顶点是相邻的。

每条证明字符串（有效或无效）对应的接受运行集形成一个团，并且所有最大团都是这样形成的。如果这些团中的一个对应于许多证明检查程序接受的证明字符串，则它被认为是巨大的。如果可满足性问题的初始实例为真，则它将拥有一个有效的证明字符串，并且所有检查程序迭代都会接受它，并且该字符串将映射到图中的一个巨大团。如果初始实例不满意，则所有证明字符串都是错误的，每个证明字符串都有有限数量的检查程序运行错误地接受它，并且所有团都很小。

因此，如果能准确近似团问题或在多项式时间内区分具有大团的图和所有团都很小的图，那么将此近似应用于从可满足性实例生成的图将允许区分可满足实例和不可满足实例。然而，除非 P = NP，否则这是不可行的。