复杂度类 P

P 是复杂度理论的粗粒度“可高效判定”基线。它表达存在一个最坏情况下的确定性多项式算法，不评价这个算法的常数、次数、缓存行为或现实输入分布。$n^{100}$ 形式上属于多项式时间，${1.01}^n$ 则不是；在有限规模上，后者完全可能先跑得更快。

图中的 $n^{100}$ 与 ${1.01}^n$ 是时间预算的增长示意，不是两个语言。某个语言已有指数时间算法，并不能据此断定它不属于 P，因为它仍可能有另一种多项式时间算法。

这个基线的价值来自闭合性和模型稳健性，而不是“多项式总是实用”的经验判断。若任务的输出不是一个是/否位，就应先明确其判定版本或另用函数复杂度类，不能仅凭口语上的“容易求解”把它放进 P。

显式图上的连通性 ​

对无向图的邻接表编码，判定给定顶点 $s,t$ 是否连通时，可以维护一个已访问标记数组和队列，从 $s$ 开始逐边扩展。每个顶点入队至多一次，每条边被检查至多两次，RAM 模型上的时间为 $O(|V|+|E|)$。邻接表的位长度至少足以写下这些顶点与边；编号比较和寻址即使在位模型或多带图灵机上增加多项式开销，仍给出 P 成员性。这里使用的是显式列出邻接表的输入；若一张指数大图由小电路隐式描述，逐顶点搜索便未必是编码长度的多项式。

伪多项式算法没有自动证明 P 成员性 ​

0–1 背包的常见动态规划按容量建立 $W+1$ 列，时间为 $O(nW)$。若 $W$ 用 $m$ 位二进制表示，$W$ 可接近 $2^m$，于是该算法关于输入长度可能是指数时间。这只否定了“这份 DP 给出多项式上界”，既不是背包困难性的证明，也不能把数值 $W$ 当成编码长度。

保证的边界 ​

启发式在常见实例上快速、随机算法以高概率快速、或某个实现的平均时间良好，都不是 P 定义要求的确定性最坏界。整数改用一元编码可能让原本伪多项式的算法变成输入长度的多项式，但那已经是不同的编码语言。P 也不应与按多数接受概率定义的 PP 混淆。

完整容量 DP：状态、回溯与二进制账单 ​

把前述背包例子的计费展开。输入显式列出 $n$ 件物品，重量 $w_i$、价值 $v_i$ 与容量 $W$ 都是非负整数，每件至多选一次。令 $A_i[c]$ 表示只用前 $i$ 件、总重量至多 $c$ 时的最大价值。容量不是要求恰好装满，因此 $A_0[c]=0$ 对所有 $0\le c\le W$ 成立；转移为

这个 动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。把可行子集按是否包含第 $i$ 件分成两类。不选时最优值为上一行同容量；选时删除第 $i$ 件后，只剩前 $i-1$ 件与容量 $c-w_i$。两类覆盖全部可能且互斥，取最大即得递推；从第 0 行归纳，最后 $A_n[W]$ 是真正最优值。每个选入项只读取上一行，零重量正价值物品也不会被重复选取。

对 $W=5$、物品 $(4,10),(3,8),(2,6)$，完整表为

回溯从 $(i,c)=(3,5)$ 开始。因为 $14>10$，选第 3 件，来到 $(2,3)$；因为 $8>0$，选第 2 件，来到 $(1,0)$；不选第 1 件，得到 011。相等时固定不选即可保留最优值。保存所有行或父决策支持这次回溯；若只用两行滚动存储，需要另加重算或决策保存，不能声称最优值滚动数组自动附带完整见证。

现在固定一种具体自分隔编码：令 $\ell (0)=1$，正整数 $a$ 的 $\ell (a)$ 为二进制位数，把每个 $a$ 编成 $1^{\ell (a)}0\mathrm{bin}(a)$，占 $2\ell (a)+1$ 位。先写 $n,W$，再按顺序写每个 $(w_i,v_i)$；因此完整输入长度恰为

本例各字段长度依次为 $5,7,7,9,5,9,5,7$，合计 54 位。表有 $(n+1)(W+1)=24$ 格，除第 0 行外计算 $n(W+1)=18$ 格，其中 9 格真正比较了选入与不选两项。这些格数不能改叫“54 位输入上的线性时间”。

若只统计表访问和整数加比较，初始化加填表需 $O((n+1)(W+1))$ 次操作。令 $V=\sum _i{v}_i$，每个价值项占 $b_V=\lceil {\log }_2(V+1)\rceil +1$ 位；下标与计数器还需 $O(\log (n+W+2))$ 位。取 $b=b_V+\lceil {\log }_2(n+W+2)\rceil$，则在显式收费的位实现中，可给出 $O(N^2+(n+1)(W+1)b)$ 的保守时间上界。实现先对每件检查 $w_i>W$：超重时直接复制整行，只有 $w_i\le W$ 才进入偏移扫描；读取和预检任意长重量字段的成本纳入前面的 $O(N^2)$。这里可用固定多带的顺序扫描：上一行复制为两份，分别以容量 $c$ 和偏移 $c-w_i$ 的位置顺次读，产生新行；复制、归位与跳到起始偏移都至多扫描一行，故不需假定随机定位任意大数组为常数时间。保留完整表需 $O((n+1)(W+1)b_V)$ 位，求值的滚动行只需 $O((W+1)b_V)$ 位，另加输入与计数器。

当容量改为 $W=2^m$ 而物品数、重量、价值保持常数时，上述编码长度只随 $m$ 线性增长，未经缩减的容量表却含 $2^m+1$ 列。这是这份算法的指数规模实例，不是所有背包算法的下界。实际实现可先把 $W$ 截为 $min(W,\sum _i{w}_i)$；要观察截断后仍会膨胀的输入，可同时取两件重量 $2^{m-1}$、价值 1 的物品，容量仍为 $2^m$，完整位长仍为 $O(m)$，而这一 DP 的列数仍指数大。

$n=0$ 时空集最优；$W=0$ 时仍可选零重量正价值物品。把数值改为一元编码，输入自身就容纳了与数值成比例的符号，原本的伪多项式界可变成新编码长度的多项式。这说明编码会改变计费语言，却没有改变同一批子集的可行性。相关的强、弱数值困难条件见 NP 困难性理路NP 困难性NP-hardnessNP 中每个语言都可多项式时间归约到目标问题。；FPTAS 缩放理路通过缩放构造 FPTASFPTAS via scaling · value scaling FPTAS通过缩放并向下取整数值，把背包的伪多项式动态规划转为对输入规模与精度均多项式的方案。保留原重量、缩小价值下标，凭的是完整误差证明，不能从“有 DP”直接跳到近似方案。

P 对补、并和交封闭：运行原判定器后交换接受与拒绝即可判定补语言；顺序运行两个判定器并组合结果，只会相加多项式时间。每台确定性机器也可视为不分支的非确定性机器，因此

这项包含是否严格，仍是未解决的 P 与 NP 问题。时间为多项式必然只访问多项式个工作格，所以还有 $\mathbf{P}\subseteq \mathbf{PSPACE}$；当前同样不知道 P 是否等于 PSPACE。

在已知精确算法仍不实用时，近似比理路近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。、参数化问题理路参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。和Meet-in-the-Middle理路Meet-in-the-MiddleMeet-in-the-middle枚举两半指数状态并以排序或哈希匹配，用空间把枚举指数减半。分别改变解质量、复杂度参数或指数搜索结构。这些是三种不同的算法承诺，不能由“属于 P”或“尚无 P 算法”替代。

NP理路复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。把基线从确定性求解改为多项式时间验证，形成后续归约与完全性理论的入口。

平均情形复杂性理路平均情形复杂性与分布归约Average-case complexity用运行时间的正阶矩定义稳健的平均多项式保证，并证明概率支配的定长归约保持该保证，复算稀有慢实例的成本。把输入分布加入问题，按运行时间正阶矩度量，并证明带概率支配的归约保持性。描述复杂性理路描述复杂性：ESO、最小不动点与有序结构Descriptive complexity在显式编码的有限结构上，用 ESO 三染色与 LFP 可达性连接逻辑表达和计算复杂性，并说明固定公式及输入顺序的作用。则在显式编码的有序有限结构上，用固定 FO(LFP) 公式刻画 P；其可达性算例展开全部迭代，并说明固定公式与输入顺序的作用。