完全性的两个条件
NP完全性是一个判定问题在给定归约方式下的复杂度性质。通常采用多项式时间多一归约：变换输入后保持是、否答案一致。语言B为NP完全，必须同时满足B属于NP，以及对每个NP语言A都有A≤pB。后一个条件单独称为NP难。
属于NP意味着肯定实例存在长度至多为输入长度多项式的证书，并可在多项式时间内核验。NP难则表示B足以承接整个NP类的困难。两个条件分别提供上界与相对下界，只有归约而没有成员资格证明，不能自动宣布NP完全。
SAT与团的核验
布尔可满足性问题SAT询问某公式是否有使它为真的赋值。给定赋值后，沿公式求值即可检查，因此SAT属于NP。Cook–Levin定理进一步证明每个NP语言都可归约到SAT，从而给归约链提供了起点，而不是仅仅观察到SAT似乎难解。
团问题的输入是无向图G和整数k，询问是否有k个顶点两两相邻。证书可列出这k个不同顶点，核验器逐对检查边。对含m个子句的3CNF公式，可为文字出现建立顶点，只连接来自不同子句且不矛盾的文字；把目标团大小设为m。
归约如何传递困难
若公式可满足，可从每个子句选一个为真的文字，所选顶点构成m元团；反之，m元团必须每个子句各取一个顶点，而且没有互相否定的文字，因此能扩充成满足赋值。这给出了3SAT到团问题的多项式归约，配合3SAT的NP完全性和团的可核验性，得到团的NP完全性。
证明新问题困难时，方向应是已知完全问题归约到新问题。归约可复合，所以不必为每个NP语言分别重新构造变换。若任何一个NP完全问题存在多项式时间算法，所有NP问题都可先归约再求解，便有P=NP。
完全性结论的边界
NP并不是“非多项式”的缩写；NP完全问题是否存在多项式时间算法，仍取决于尚未解决的P与NP问题。即使假设P≠NP，也只排除了多项式时间总算法，不能单凭完全性断言必须耗费某个确定形式的指数时间。
“寻找最大团”是优化问题，“是否存在至少k个顶点的团”才是这里的判定版本。优化问题常被称为NP难，但不能不作说明就与判定语言的NP完全性等同。不可判定问题也不属于NP完全语言，因为NP问题可通过有限枚举证书来判定。
这些定义采用最坏情形，并不否认某些输入很容易、某些受限结构有快速算法，或工程求解器能处理大量实际实例。完全性提醒人们审视普遍高效算法的可能性，而不替代对具体数据分布、近似目标和参数范围的分析。