P 类问题是"合理时间可解"的分界线

如果一个问题存在时间复杂性受多项式表达式（如 n、n²、n³）约束的算法，就称它属于 P 类（多项式问题），意味着它能在合理时间内解决；反之，如果一个问题的每一种解法复杂性都是指数级的（如 2ⁿ），哪怕理论上”可解”，随着输入规模增长，所需时间也会迅速膨胀到任何计算机都无法承受的地步——这类问题被称为难解的。比如枚举 n 个人所有可能的分组方案，方案数本身就是 2ⁿ-1 个，无论用什么算法输出这些方案，耗时都注定随 n 指数增长。发散：P 类的意义在于把”理论上有解”和”实际上能用”这两件看似相近的事清楚地区分开来——一个问题被证明”可解”只保证存在算法，完全不保证这个算法能在人类能接受的时间尺度内跑完，这也是为什么计算机科学家格外看重”是否属于 P”这个问题，它才是决定一个问题能不能被现实中的计算机真正解决的关键分界线。