NP-Completeness
NP 完全问题属于 NP 且所有 NP 问题可多项式归约至它，是最难的 NP 问题。
用途
理解计算复杂度层级，识别难解问题。
机制
NP：可在多项式时间验证。NP-hard：所有 NP 可归约至它。NPC=NP∩NP-hard。若任一 NPC 有多项式解则 P=NP。经典：SAT、TSP、顶点覆盖。
用例
- 复杂度分析
- 问题难度评估
- 归约证明
NP 完全问题属于 NP 且所有 NP 问题可多项式归约至它，是最难的 NP 问题。
理解计算复杂度层级，识别难解问题。
NP：可在多项式时间验证。NP-hard：所有 NP 可归约至它。NPC=NP∩NP-hard。若任一 NPC 有多项式解则 P=NP。经典：SAT、TSP、顶点覆盖。