Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 262: Computational Complexity Homework 4
1. Show that the class ZPP = RP ∩ co − RP.
2. Describe a decidable language that is in P/poly but not in P.
3. A language L ⊆ {0, 1} ∗ is sparse if there is a polynomial p such that |L∩{0, 1} n | ≤ p(n) for all n. Show that every sparse language is in P/poly.
4. The class P/log is the class of languages decidable by a Turing Machines running in polynomial time that take O(log n) bits of advice. Show that SAT ∈ P/log implies P = NP. 1