O(n²)时间可找到Maximal Clique？这是否能证明P=NP？

结论先行 #

你对文章内容的理解没有偏差，但该结论完全不能证明P=NP，核心原因是你混淆了两个高度相似的核心概念：极大团（Maximal Clique）和最大团（Maximum Clique）。

概念差异说明 #

• 极大团：指无法再向其中加入任意一个图中的其他顶点，还能保持团的性质（团内所有顶点两两之间都有边相连）的团。找任意一个极大团确实存在多项式时间解法，你提到的O(n²)贪心实现是完全可行的：随便选一个顶点作为初始团，不断遍历剩余顶点，把和当前团所有顶点都相连的顶点加入，直到没有符合条件的顶点为止，这个过程的时间复杂度上限就是O(n²)。
• 最大团：指图中包含顶点数量最多的团。我们常说的NP完全的「团问题」，指的就是最大团相关判定/求解问题：给定图G和整数k，判断G中是否存在大小≥k的团，或是直接求解G的最大团大小。该问题目前没有被证明存在多项式时间解法，也是P=NP猜想的核心待证问题之一。

补充说明 #

这是团问题领域非常常见的入门误区，两个术语中文仅差一个字，英文也只有前缀差异，但计算复杂度的差距是本质性的。

内容的提问来源于stack exchange，提问作者user17214152