P

我们可以将所有计算问题分为两类，一类可以通过算法解决，另一类无法解决。虽然有些问题可以解决，但我们可能无法在合理的时间内解决它们。可以解决的问题分为 P 和 NP 类。还有其他分类，但我们将重点关注 P 和 NP。这些分类称为复杂度类。一般来说，P 类包含可以在合理时间内解决的问题，而 NP 类包含那些无法解决的问题。

复杂度类 P

${\text{P}}=\bigcup _{k}{\text{TIME}}(n^{k})$

复杂度类 P 包含可以在有限时间内解决的问题。解决此类问题的算法受输入大小的多项式函数限制。复杂度分为两部分，固定部分和可变部分。固定部分与其他任何东西无关，对于给定算法来说是一个常数，但可变部分在同一问题的不同实例中会有所不同，例如，我们知道排序算法对十个数进行排序所需的时间与对一百个数进行排序所需的时间不同。通常算法所需的时间/空间将取决于问题的输入大小。我们可以将算法所需的时间/空间表示为常数和输入大小的多项式函数之和。那些其解决算法的复杂度可以用多项式表示的问题属于 P 类。显然，P 代表多项式。