团（clique）问题

实例： $G=(V, E)$，一个非负整数$J<=|V|$

询问： 是否存在 $V$ 的子集 $V'\subseteq V$，$|V'|\geq J$，使任意$u, v\in V'$，总有$(u,v)\in E$。 也即在图 $G$ 中找一个点数大于 $J$ 的完全图（当然，也是子图）。

该问题的证明可以通过独立集问题归约证明。

NPC 证明

定理：原图中有一个大小为 $J$ 的独立集，当且仅当原图的补图中存在一个大小为 $J$ 的完全图。

分析：因为独立集要求集合中任意两点之间没有边，因此对应到补图中时，任意两点之间就都有边，即完全图。

因此独立集问题可以等价于其补图的团问题。