Problem 3 (35 points).

Consider a CNF formula like so F(x1, . . . , xn) = ^ j[m] Cj We call a CNF formula (w, k)-restricted if every clause Cj has width at most w, and every variable xi occurs in at most k clauses (in positive or negated form). As usual, say that such a formula is satisfiable, if there exists an assignment y {0, 1} n to the variables x such that F(y) = 1. For example, the formula F = (x1 x3) (x1 x4 x5) is (3, 2)-restricted. It is also (3, 10)-restricted, since the former immediately implies the latter. Fix a reasonable natural encoding hFi of such formulas and let (w, k)-restricted sat denote the language consisting of all strings of form hFi, where F is a satisfiable (3, 10)-restricted CNF formula. Prove that (w, k)-restricted sat is NP-complete. We note that the constant 10 in the statement is chosen to give some slack in the proof; the statement can be proved with a smaller number in place of 10.