[30]

(a) Show that for 0 ≤ x

(b) Prove that there is some polynomial p such that for all formulas

φ(x1,...,xn) ∈ SAT and all r such that l(r) = p(l(φ)) and C(r) ≥

l(r), there is some satisfying assignment a of (x1,...,xn) such that CDp(a|φ, r) ≤ O(log n).

Comments. Hint: see the proof of Theorem