Skip to main content

1 / 4概念

Computational Complexity

计算复杂性回答的是“这个问题在多项式时间内可解吗”。它不讨论某段代码快不快,而是给问题本身分类:P 是可解的,NP 是可验证的,NP 完全是最难的一类;判断标准不是“这题看起来难”,而是能否写出验证器、能否从已知难问题归约。

1 概念​

1.1 一句话定义​

计算复杂性按资源(时间、空间)给可判定问题分类。P 是确定性图灵机多项式时间可解的问题;NP 是给定证书后多项式时间可验证的问题;NP 完全是 NP 中最难的一类,NP 难是所有 NP 问题都能多项式归约到的问题。

1.2 它解决什么问题​

  • 判断该不该找多项式算法:NP 难问题通常不该继续找通用精确解,而应转向近似、参数化或启发式。
  • 选择求解策略:小 n 精确、可接受误差近似、固定参数 FPT、工程启发式。
  • 沟通难度:用“NP 完全”而不是“这题很复杂”描述问题,让团队对预期一致。
  • 识别伪多项式:O(nW) 看起来是多项式,但对输入位数是指数,不能当成 P。

没有这套分类,团队会在 NP 难问题上反复尝试“再优化一下”,而真正该做的是改问题或改算法目标。

1.3 不属于本页的内容​

主题去哪
可判定性、停机问题、Rice 定理Computability
单个算法的渐进分析与摊还Complexity Analysis
具体图算法的流程Graph Algorithms
近似算法的完整设计与分析近似算法页面(待补)
SAT 求解器、ILP 求解器的工程调优求解器工程页面(待补)

1.4 关键术语​

术语含义容易混淆的点
判定问题输出是/否的问题不是优化问题本身
优化 / 搜索问题求最优值 / 求一个解可转成判定问题
证书用来验证“是”的短证据不是求解过程
P确定性多项式时间可解不是“实际很快”
NP多项式时间可验证不是“非多项式”
co-NP补集在 NP 中不是 NP 的补集类名
多项式归约用多项式时间映射实例不是调用求解器
NP 难所有 NP 问题都可归约到它不要求它自己在 NP
NP 完全NP 难且在 NP 中是最难的一类,不是“不可解”
弱 NP 难存在伪多项式算法子集和是典型
FPT固定参数下多项式时间参数必须小