[20]

(a) Show that a set S is sparse iff for all x ∈ S, CDp(x|S) ≤

O(log l(x)) for some polynomial p.

(b) Show that set S ∈ P is sparse iff for all x ∈ S, CDp(x) ≤ O(log l(x))

for some polynomial p.

Comments. Use Theorem 7.2.1.

Source: [H.M. Buhrman and L. Fortnow, Proc. 14th Symp. Theoret. Aspects Comput. Sci., Lect. Notes Comput.

Sci., Springer-Verlag, 1997; H.M. Buhrman, L. Fortnow, and S. Laplante, SIAM J. Comput., 31:3(2001), 887–905]. The authors also define a nondeterministic version of CD and prove several results.