P 类

P 类问题是单带确定 TM 在多项式时间内可判定的问题, 即 $P={\bigcup }_{k}TIME(n^k)$.

• 对于所有与单带确定 TM 等价的模型, P 不变.
• P 大致对应于在计算机上实际可解的问题, 研究的核心是一个问题是否属于 P 类.