时间复杂性

Turning机的时间复杂度
定义. 设有DTM U，字母表为A，并假设U总停机。对于\(w\in A^*,\)把U对w计算中的步数记作\(t_U(w)\), 称为U关于w的计算时间。称\[t_U(n) = \max\{t_U(w)|w\in A^*,|w|\le n\}\]为U的时间复杂度。
注意，这里的\(t_U(n)\)是相对于所有长度不超过n的输入中，最大的计算步数，也就是最坏情况下所需的计算时间。

而对于NTM U，也有类似定义，只需要修改\(t_U(w)\)为所有可能的计算中，最长的计算时间，而\(t_U(n)\)的定义同上。

一般地，我们可以用全函数\(t:N\to N\)来刻画\(t_U(n)\)的性质。如果\(t_U(n) = O(t(n)),\)称\(t(n)\)为U的时间复杂度上界，U是\(t(n)\)时间界限的。

定理1. 设U是t(n)时间界限的多带DTM(NTM), 则存在\(t^2(n)\)时间界限的单带DTM(NTM)U'使\(L(U')=L(U).\)
定理2. 每个t(n)时间的NTM都与一个\(2^{O(t(n))}\)的DTM等价。

定理1说明，多带TM的时间复杂度可以平方转化到单带上，而平方运算在多项式类或指数类中封闭。这说明，在同一时间复杂性类中，总可以不妨假定TM是单带的。下面给出时间复杂性类的具体定义。

定义. 时间复杂性类\(TIME(t(n))\)是所有\(O(t(n))\)时间的图灵机判定的所有语言的集合。其中，用DTIME，NTIME分别表示DTM和NTM对应的判定语言。
定义. P是DTM在多项式时间内可判定的语言类，即\[P= \bigcup_k DTIME(n^k).\]而NP表示NTM在多项式时间内可判定的语言类，即\[NP= \bigcup_k NTIME(n^k).\]
NP类的一种等价定义是“多项式可验证的”，指存在一个字符串c(又称为资格证书或证明)，来验证w是A的成员。形式化描述如下：
定义*. 语言A的验证机是一个算法V，使得\[A=\{w|\exists c ,\langle w,c \rangle \in F(V).\}\]如果V能在|w|的多项式时间内运行，称V为一个多项式时间验证机。全体具有多项式时间验证机的语言，记为NP类。注意，NP类里A的定义中一定满足\(\exists k , |c| = O(|w|^k).\)

总而言之，如果我们认为多项式时间可判定的算法是“快速的”，那么可以有如下理解：
P类是成员资格可以快速判定的语言类；
NP类是成员资格可以快速验证的语言类。

    所属分类：TCS     发表于2021-12-14