作者EternalChaos (永远的混沌)
看板NTU-Exam
标题[试题] 100下 王柏尧 计算理论 期末考
时间Wed Jun 20 16:11:19 2012
课程名称︰计算理论
课程性质︰系必选
课程教师︰王柏尧
开课学院：管理学院
开课系所︰资讯管理学系
考试日期（年月日）︰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