課程名稱︰ 高等計算理論
課程性質︰ 研究所選修
課程教師︰ 顏嗣鈞
開課學院： 電資學院
開課系所︰ 電機所
考試日期（年月日）︰ 2003/04/18
考試時限（分鐘）： 3hr
試題 :
(【 and《 stand for polynomial-time many-one reduction
and polynomial-time Turing reduction, respectively.)
1. 15pts
Define what fully space constructible functions mean. Prove in sufficient
detail that the function f(n)=n^2 is fully space constructible.
2. 10pts
Prove the following:
(a) A【 B, B【 C → A【 C
(b) A《 B → A【 C
3. 15pts
Prove that L【 L' and L'\in Σ, then L\in Σ (Σ is the n-th level of the
polynomial time hierarchy)
4. 15pts
Prove that BPP\subseteq PSPACE. (For each L\in BPP, show how a PSPACE
TM M can be constructed such that L(M)=L)
5. 15pts
For any class of language C, coC={\bar{L}|L\in C}. Prove that
NP\cup coNP \subseteq P^{SAT} (where P^{SAT} is the class of languages
accepted by polynomial time DTMs using SAT as oracles)
6. 15pts
Suppose we define the acceptance condition of BPP_{a/b} to be
"Pr[M(x)\neq \chi(x)]<1-(a/b)." Prove that BPP_{2/3} \subseteq BPP_{9/10}
7. 10pts
Prove that if a language L is in coNP, then L can be accepted by an
alternating TM for which all states are universal
8. 5pts
Prove that if L is in NP, then the language L*={w1w2...wk|there exist k\in N,
wi\in L, 1≦i≦k} is alsoin NP
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.180.216