These hints can give you a nudge if you are stuck on a problem. I recommend trying the problems without hints for at least a couple days before you look. If you're still stuck after looking at the hints, ask on Piazza.

Click to reveal hints.

Problem 2

• Hint 1 (Idea for B_k)

  Use an idea from the Goldwasser-Sipser protocol (Lecture 9).
• Hint 2 (Followup to hint 1)

  Hash the variable assignment into an appropriately-sized bucket. Can you lower-bound the probability that there's a unique solution to ϕ which hashes to 0?
• Hint 3 (Making it a formula)

  Any polynomial-time algorithm can be encoded as a SAT formula. (There's a famous theorem based on this idea.)

Problem 3

• Hint 1 (The meaning of "small")

  2^l/(100⋅l) is small enough.
• Hint 2 (The meaning of "large")

  (99/100)⋅2^l is large enough.