作者dennis2030 (綠豆)
看板NTU-Exam
標題[試題] 102-1 資訊工程理論基礎 呂育道 期中考
時間Tue Nov 5 10:56:26 2013
課程名稱︰資訊工程理論基礎
課程性質︰必修
課程教師︰呂育道
開課學院：電資學院
開課系所︰資工所
考試日期（年月日）︰2013/11/05
考試時限（分鐘）：180min
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Problem 1 (25 points)
Show that if NP != coNP, then P != NP
Problem 2 (25 points)
It is known that H* = {M|M halts on all inputs} is undecidable.
Show that L is undecidable, where
L = {M1,M2|M1 and M2 are TMs and M1(x) = M2(x) for all inputs x}.
Problem 3 (25 points)
Prove that the language CNP is NP-complete,
where CNP ={(N,x,0^t)| N is an NTM that accepts x within time t}.
Recall that 0^k denotes the string consisting of k 0s. Do not forget to
show CNP is in NP.
Problem 4 (25 points)
We say that a function f:Z+ -> Z+ is a
proper complexity function if
1. f is non-decreasing, i.e, f(n+1)≧f(n) for all positive integers n.
2 There is a k-string Turing Machine Mf with input and output that,
given an input of length n,
—＞ output，符號打不出來
|
(a) outputs Π^f(n) on its output string in time O(n+f(n)), and
(b) uses O(f(n)) space besides its input and output
Show that the set of proper complexity functions is closed under sums(i.e.,
if f and g are proper complexity functions, then f + g is also a proper
complexity function.)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.29.130
※ 編輯: dennis2030 來自: 140.112.29.130 (11/05 10:57)