复杂度类 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 混淆。

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；其可达性算例展开全部迭代，并说明固定公式与输入顺序的作用。