作者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