时间层次定理

时间层次定理《理论计算机科学基础》1《理论计算机科学基础》2时间可构造时间可构造函数t:N

N满足t(n)nlogn并且t(n)在O(t(n))时间内可计算输入1n,输出二进制f(n)存在TM以t(n)作为时间复杂性《理论计算机科学基础》3例10.9nlogn,nn,n2,2n,…都是时间可构造的《理论计算机科学基础》4带时间限制的通用机设t(n)是时间可构造的,s(n)logs(n)=o(t(n)),或s(n)=o(t(n)/logt(n)),则存在TMU在t(n)时间内运行,并且对于在s(n)时间内运行的任意TMM和足够长的输入w,U在输入<M,w>上模拟M在输入w上的计算,即U(<M,w>)=M(w).U字母表固定,M字母表任意,U用d个格子表示M的一个格子,U使用时间ds(n)logs(n)模拟M,存在n0,当n

n0时,ds(n)logs(n)<t(n).《理论计算机科学基础》5带时间限制的TM的列表设t(n)是时间可构造的,并且s(n)=o(t(n)/logt(n)),则可列举出TMM1,M2,M3,……,使得TIME(s(n))

{L(M1),L(M2),L(M3),……}.设全体TM的枚举是N1,N2,N3,……给上述每个TM增加“时钟”,

对于足够长的输入,

控制其运行时间不超过t(n)对于较短的有限个输入,

把答案“固化”在TM里,

就得到M1,M2,M3,……《理论计算机科学基础》6对角化TMB=“对输入w:1)令n是w的长度.2)利用时间可构造性计算t(n),把值

t(n)/logt(n)保存在二进制计数器里.

每执行一次步骤3,4,5之前把该计数器减1.

若计数器减到0,就拒绝./*时钟*/3)如果w不形如<M>10*,M是TM,则拒绝.

/*padding*/4)在w上模拟M.5)若M接受,则拒绝;若M拒绝,则接受.”

/*对角化*/《理论计算机科学基础》7时间层次定理定理10.10:对任何时间可构造函数t,存在语言A,在O(t)时间内可判定,但不能在o(t/logt)时间内判定.证明思路构造一个语言A

A

TIME(O(t(n))),ATIME(o(t/logt)),对角化《理论计算机科学基础》8定理10.10证明证明:TMB=“对输入w:1)令n是w的长度.2)利用时间可构造性计算t(n),

执行下列步骤

t(n)/logt(n)步.

若在这个步数内还没有执行到

步骤5,就拒绝.3)如果w不形如<M>10*,M是TM,

则拒绝.

4)在w上模拟M.5)若M接受,则拒绝;若M拒绝,则接受.”《理论计算机科学基础》9定理10.10证明证明(续):B采用3条轨道,一条存储M的带内容,一条存储M的当前状态和转移函数的副本,一条存储二进制计数器.B在常数时间内模拟M的一步,

一共模拟

t(n)/logt(n)步.

B每模拟M的一步,就在logt(n)时间内给计数器减1,所以B是O(t(n))时间的.设A=L(B),则ATIME(O(t(n))).

《理论计算机科学基础》10定理10.10证明证明(续):下证ATIME(o(t(n)/logt(n))):(反证)设A=L(M)且M在g(n)时间内运行,g=o(t/logt).B需要dg(n)时间模拟M,d是只与M有关的常数.设nn0时有dg(n)<t(n)/logt(n),

则B可以完成对M的模拟,<M>10n0

L(M)<M>10n0

L(B),即<M>10n0

A<M>10n0

A,矛盾!#《理论计算机科学基础》11推论推论10.11:设函数t2(n)是时间可构造的,并且函数t1(n)=o(t2(n)/logt2(n)),则