Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 262: Computational Complexity Midterm Exam
Important note: Please remember that you should not discuss this exam with anone else or search the internet to look for solutions.
1. Show that if NP ⊆ BPP then RP = NP.
2. Show that if f(n) ≥ n and g(n) ≥ n, are proper functions, then TIME(f(n)) = NTIME(f(n)) implies that TIME(f(g(n))) = NTIME(f(g(n))).
3. Suppose that L1, L2 ∈ NP. Is L1 ∪ L2 in NP? What about L1 ∩ L2? Prove your answers.
4. A complexity class C is closed under complement if L ∈ C implies that co − L ∈ C.
(a) Are BPP or ZPP closed under complement? Justify your answer.
(b) If either RP or co-RP are closed under complement then which complexity classes (among the ones we have defined in class) are equivalent to RP?