Computer Science 531 Spring 2022 Homework Set 4B
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computer Science 531
Spring 2022
Homework Set 4B
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
(b) PmpEXPq
(c) PmpEq
Problem 32.
(a) What is PmpNPq?
(b) Prove that NP ‰ E .
2022-04-28