===========================================================================
CSC 363                     Homework Exercise 5                 Winter 2008
===========================================================================

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 = { 1^p : 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 u 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.