CSE 6321: Assignment 4
Due: 11:59pm Thursday, April 22nd
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)
1


















学霸联盟