Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 6321: Assignment 4
1. (25 points) Prove that for every constant c > 0, there exists a language L ∈ Σp3 such that L 6∈ SIZE(nc). (hint: builds on Shannon’s theorem for existence of functions that require large circuits.) 2. (15 points) Build on problem 1. to prove the stronger statement: For every constant c > 0, there exists a language L ∈ Σp2 such that L 6∈ SIZE(nc). (hint: based on whether NP has polynomial-size circuits) 3. (15 points) Suppose C is a randomized circuit over n inputs (that is, C is chosen according to some distribution over the set of circuits over n inputs). We say that C is of size at most s if with probability 1, size of C is at most s. We say that a language L ∈ {0, 1}∗ has a randomized polynomial-size circuit family, if is a polynomial p and a p(n)-size randomized circuit family C1, C2, . . . such that for every n, and x ∈ {0, 1}n, x ∈ L⇒ Pr[Cn(x) = 1] ≥ 2/3, and x 6∈ L⇒ Pr[Cn(x) = 1] ≤ 1/3. Prove that every language that has a randomized polynomial-size circuit family is in fact in P/poly. (hint: reduce the error probability)