Problem 29. A language A Ď Σ˚  is sparse, and we write A P SPARSE, if there is a polynomial q such that, for all n P N,

|A X Σn | ď qpnq

(a) Prove that SPARSE is uncountable.

For each n P N, let w,w be the enumeration of Σn  in standard order.  For each A Ď Σ˚ and n P N, define the string

χ“npAq “ b0 b1 ...b2n ´1 P Σ2n

by

bk  “

for all 0 ď k ă 2n .

(b) Prove: If A P SPARSE, then

n(l)imÑ8           2n             “ 0

Problem 30. Simplify the following four expressions, and prove that your answers are correct. (a) DP DEC

(b) DP NP

(c) DP

(d) @P

Problem 31. For each language A Ď Σ˚ , let

PmpAq “ tB Ď Σ˚  | B ďm(P) Au

For each class C of languages, let

PmpCq “      PmpAq

APC

Simplify the following expressions, and prove that your answers are correct.

(a) PmpPq