課程名稱︰計算理論
課程性質︰系必選
課程教師︰王柏堯
開課學院：管理學院
開課系所︰資訊管理學系
考試日期（年月日）︰101/06/20
考試時限（分鐘）：三節課
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Final
Theory of Computation Spring 2012
(1) Recall
SAT = {<ψ>:ψis a satisfiable Boolean formula}.
Show that SAT ≦m {0}. (20%)
(2) Recall
Etm = {<M>: M is a TM and L(M) = ψ}.
_
Show that Etm is Turing-recognizable. (20%)
_
(3) Let A 屬於 P. Show that A 屬於 P. (20%)
(4) Consider
ALLSAT = {<ψ>:ψ is a Boolean formula satisfied by every assignment}.
Show that ALLSAT 屬於 P implies SAT 屬於 P. (20%)
(5) Recall NP 包含於 PSPACE and
_
coNP = {A:A 屬於 NP}.
Show that coNP 包含於PSPACE. (20%)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.245.126