复杂度类 P

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

这个基线的价值来自闭合性和模型稳健性，而不是“多项式总是实用”的经验判断。若任务的输出不是一个是/否位，就应先明确其判定版本或另用函数复杂度类，不能仅凭口语上的“容易求解”把它放进 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由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。把基线从确定性求解改为多项式时间验证，形成后续归约与完全性理论的入口。