判定问题的多项式时间类
P是确定性多项式时间复杂度类，包含所有能由确定性图灵机在输入长度n的多项式时间内判定的语言。形式上，它是所有固定常数k对应TIME(n^k)的并集。判定要求对每个输入都停机，并正确回答成员资格，而非只在肯定实例上保证返回结果。
P描述问题是否存在某个符合条件的算法，不是给某一段程序贴标签。一个问题可以同时有低效穷举算法和高效算法，只要后者存在，它就属于P。反过来，发现当前程序很慢，不足以证明该问题不在P。
数值大小与编码位长
时间界中的n是输入编码的长度。一个整数N采用二进制表示时约需log₂N位，因此一个执行N次循环的程序，虽然对数值N是线性的，却可能对输入位长呈指数增长。评价所谓多项式算法时，必须先说明输入如何编码。
二进制和十进制等通常的定位记数法可以在多项式时间内互相转换，因此不会因为换用这两种基数就改变P的成员资格。一元编码则可能把同一整数写成极长字符串，这会改变长度尺度，不能把所得结论无条件搬回紧凑编码的版本。
参考：[2]
复合与模型稳健性
多项式时间适合作为统一尺度，一个原因是它能容纳子程序组合。若主程序进行多项式次操作，每次调用的子程序也在有关输入长度的多项式时间内结束，而且中间输入长度保持多项式，合起来仍是多项式。这使算法分析不必把每个合理的底层操作都重新展开。
在常见经典计算模型之间，例如固定带数的图灵机变体，模拟开销至多为多项式，所以是否属于P不会因这些常规改变而动摇。稳健性不等于所有设想中的机器都自动等价；若允许单位时间处理无限精度数值等异常能力，就必须重新审查资源计费。
参考：[1]
理论可行与实际可行
图可达性是P中的典型判定问题，可以系统扩展已经到达的顶点集合，直到找到终点或没有新顶点。确定性多项式时间核验器也可以直接运行P问题的算法而忽略证书，所以P⊆NP；是否每个NP语言都属于P，仍是开放问题。
多项式界不是实际响应时间的保证。很高的次数、很大的常数、数据布局和输入规模，都可能让一个P中的算法难以使用。相反，某个最坏情况超多项式的程序，也可能在受限数据上表现很好。P的作用是刻画随规模增长的理论边界，而不是替代基准测试或工程资源预算。