复杂性类的真包含关系

定理. 设\(s_2(n)\)空间可构造，且\(s_i(n)\ge \log_2(n).\)若\[\lim_{n\to\infty} \frac{s_1(n)}{s_2(n)}=0,\]则\(DSPACE(s_2(n))\subsetneq DSPACE(s_1(n)).\)

为此我们先引入单工作带离线图灵机编码的方法：对每个U的动作函数，构造六元组\(q_1s_bs_c\Delta_d\Delta_eq_f\)，分别对应状态、读到的两个符号、接下来的两个动作和下一个状态。然后利用0和1相建即可描述上述动作。

定理的证明思路是，构造一个\(s_2(n)\)空间界限的DTM U，对每个\(s_1(n)\)空间界限的图灵机，都不接受相同的语言，从而U接受的语言不在\(DSPACE(s_1(n))\)中。
对每个输入w，U将检查w是否是一个合法的Turning机的代码，如果不是，则拒绝。如果是，则模拟\(U_w\)对w的计算。这是对角化方法的技巧。如果\(U_w\)接受w，则U拒绝；否则接受。因此，\(U,U_w\)接受的语言总不相同。条件的用处在于，\(U\)有足够的空间模拟\(U_w\)的计算。

推论. \(NL\subsetneq PSPACE \subsetneq EXPSPACE.\)

用类似的方法可以证明：\(P\subsetneq EXPTIME.\) 构造一台U, 对每个多项式时间界限的\(U_w\)，U接受w当且仅当w是合法的DTM编码，\(U_w\)在\(2^{|w|}\)步内停机，且拒绝w。

至此，复杂性类的包含关系可以整理如下：
\(L\subset NL \subset P \subset NP \subset PSPACE \subset EXPTIME \subset NEXPTIME \subset EXPSPACE,\)
\(NL \subsetneq PSPACE \subsetneq EXPTIME,\)
\(P \subsetneq EXPTIME.\)

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