團問題（clique problem）

想像一個社群網路，邊代表兩人是朋友。團是一群其中「每個人都和其他每個人都是朋友」的群體：完美相連的一團，沒有缺漏的友誼。團問題對一張圖問一個是非題：是否存在一個大小至少為給定值 k 的團？它是「尋找一個彼此完全相連的群體」的原型問題。

形式上，在無向圖 G 中，團是一組頂點，使得其中每一對都有邊相連。判定問題 CLIQUE 接收一張圖 G 與一個數 k，問 G 是否含有一個大小為 k 的團。它屬於 NP：一組候選的 k 個頂點是證書，驗證器在多項式時間內檢查所有 C(k, 2) 對都是邊。然而尋找一個大團，似乎得在指數量級的頂點子集中搜尋，沒有已知的捷徑。

CLIQUE 是 NP 完全，由一個俐落的從 3-SAT 出發的歸約證得。由一條含 m 個子句的 3-CNF 公式，你建一張圖：每個文字出現處一個頂點，分成 m 組各三個。當兩個頂點位於「不同」子句「且」不相矛盾（不是一個變數與它自己的否定）時，就連一條邊。則公式可滿足，當且僅當這張圖有一個大小為 m 的團——從每個子句各挑一個彼此一致的真文字。CLIQUE 也和兩個手足緊緊綁在一起：G 中的團恰恰是補圖中的獨立集，而其補頂點構成一個頂點覆蓋，所以這三個問題幾乎免費地互相歸約。