時間層次定理《理論計算機科學基礎》1《理論計算機科學基礎》2時間可構造時間可構造函數(shù)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)保存在二進制計數(shù)器里.

每執(zhí)行一次步驟3,4,5之前把該計數(shù)器減1.

若計數(shù)器減到0,就拒絕./*時鐘*/3)如果w不形如<M>10*,M是TM,則拒絕.

/*padding*/4)在w上模擬M.5)若M接受,則拒絕;若M拒絕,則接受.”

/*對角化*/《理論計算機科學基礎》7時間層次定理定理10.10:對任何時間可構造函數(shù)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),

執(zhí)行下列步驟

t(n)/logt(n)步.

若在這個步數(shù)內還沒有執(zhí)行到

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

則拒絕.

4)在w上模擬M.5)若M接受,則拒絕;若M拒絕,則接受.”《理論計算機科學基礎》9定理10.10證明證明(續(xù)):B采用3條軌道,一條存儲M的帶內容,一條存儲M的當前狀態(tài)和轉移函數(shù)的副本,一條存儲二進制計數(shù)器.B在常數(shù)時間內模擬M的一步,

一共模擬

t(n)/logt(n)步.

B每模擬M的一步,就在logt(n)時間內給計數(shù)器減1,所以B是O(t(n))時間的.設A=L(B),則ATIME(O(t(n))).

《理論計算機科學基礎》10定理10.10證明證明(續(xù)):下證ATIME(o(t(n)/logt(n))):(反證)設A=L(M)且M在g(n)時間內運行,g=o(t/logt).B需要dg(n)時間模擬M,d是只與M有關的常數(shù).設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:設函數(shù)t2(n)是時間可構造的,并且函數(shù)t1(n)=o(t2(n)/logt2(n)),則