形式陈述

$$\mathbf{P}=\bigcup _{k\ge 1}\mathrm{DTIME}(n^k).$$

也就是说，语言 $L$ 属于 $\mathbf{P}$，若存在常数 $k$ 和确定性图灵机，在 $O(n^k)$ 时间内对每个长度为 $n$ 的输入判定是否属于 $L$。

直觉

P 被视为“在理论上可高效求解”的稳健基线，因为多项式时间在常见计算模型之间通常保持不变，并对算法复合封闭。

例子与边界

最短路、最小生成树和线性规划的判定版本属于 P。属于 P 不保证实际快速：多项式次数和常数仍可能很大。

推论与应用

P 是比较可验证性、随机化和并行计算能力的参照类，也是 P 与 NP 问题的一侧。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §2.1.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., §7.2.