作者edwardhw (我是大黃)
看板NTU-Exam
標題[試題] 99上 呂育道 資訊工程理論基礎 期中考
時間Sun Nov 21 02:36:54 2010
課程名稱：資訊工程理論基礎
課程性質︰必修
課程教師︰呂育道
開課學院：電資學院
開課系所︰資工所
考試日期（年月日）︰2010/11/09
考試時限（分鐘）：180分鐘
是否需發放獎勵金：是
Problem 1. (25 points) How many functions from {0, 1, 2}^n to {0, 1, 2} are
there? (Hint: Do not write a^b^c as it is not clear whether it means (a^b)^c) or
a^(b^c).)
Problem 2. (25 points) Prove that NSPACE(log^2(n)) 包含等於 TIME(2^(log^4(n))).
(Hint: You can use Savitch's theorem.)
Problem 3. (25 points) Let N be the set of natural numbers. Does there exist a
bijection between 2^N and NP?
Problem 4. (25 points) Show that it is NP-hard to determine whether a Boolean
expression in 3SAT form has at least two satisfying assignments. (Hint: What is
the property of F︿(x﹀y﹀z), where F is a 3SAT formula?)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.68.246