44.P与NP

title: 44. P 与 NP tags: zk complexity theory P class NP class WTF zk 教程第 44 讲：P 与 NP 在上一讲中，我们介绍了复杂性理论的基础概念。这一讲，我们将探讨两个最重要的复杂度类：P类和NP类。它们有助于我们理解计算问题的难度。 P类 复杂度类是具有相关复杂性的问题的集合。P类（Polynomial Time）是确定型单带图灵机可以在多项式时间内可判定的语言类。我们认为多项式时间的问题是高效的，因此P类代表可以所有被“快速”解决的问题。 1.1 P类的形式化定义 设 $t: N \to R^+$ 是一个函数，我们定义时间复杂类 $\text{TIME}(t(n))$ 为由 $O(t(n))$ 时间的确定型图灵机可以判定的所有语言的集合。例如 $\text{TIME}(n^2)$ 是由 $O(n^2)$ 时间的图灵机可以判定的所有语言的集合。 P类的形式化定义为： $$ P = \cupk{\text{TIME}(k^n)} $$ 一个语言 $L$ 属于P类，当且仅当存在一个确定性图灵机 $M$ 和一个多项式 $p...