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