Homework Exercise 5

Due: by 6pm on Wed 19 Mar
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. Show that UNARY_PRIMES = { 1p : p is prime } belongs to P. You may rely on the fact that integer division can be carried out in polytime, without having to describe how to implement it.

  2. Prove that P is closed under complementation, i.e., for all L ∈ P, L ∈ P.

  3. Prove that NP is closed under union, i.e., for all A, B ∈ NP, A ∪ B ∈ NP.

  4. Prove that ≤p is transitive, i.e., for all languages A, B, C, if A ≤p B and B ≤p C, then A ≤p C.