作者bang5115 (Bangod)
看板NTU-Exam
标题[试题] 101上 吕育道 资讯工程理论基础 期中考
时间Tue Nov 6 13:46:41 2012
课程名称︰资讯工程理论基础
课程性质︰必修
课程教师︰吕育道
开课学院：电机资讯学院
开课系所︰资讯工程研究所
考试日期（年月日）︰101/11/6
考试时限（分钟）：180
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Problem 1 (25 points)
It is known that 3-SAT is NP-complete. Show that 4-SAT is NP-complete.
(Don't forget to show that it is in NP)
Problem 2 (25 points)
Show that if there exists a language L 属於 NP not in P, then no NP-complete
langauge is in P.
Problem3 (25 points)
Show that L ≠ P or P ≠ PSPACE.
Problem 4 (25 points)
Show that {M : M halts on all inputs} is not recursive.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.252.153
1F：推 jackywang05 :(Y) 09/19 13:46