===========================================================================
CSC 363H                        Exercise 7                        Fall 2007
===========================================================================

A.  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.
    (The idea of this is quite obvious; the point of this question is to
    get you to think through the technical details and write them up
    carefully.)

B.  Prove that a language A is NP-complete iff (A <=p SAT and SAT <=p A).

C.  Recall the language HAMPATH
        { <G> : G is an undirected graph that contains a Hamiltonian path,
                i.e., a simple path that includes every vertex of G once }
    It is possible to show that HAMPATH is NP-complete.
    Now consider the language HALF-HAMPATH
        { <G> : G is an undirected graph that contains a Hamiltonian path
                on half of its vertices, i.e., there is some simple path
                v_1 -- v_2 -- ... -- v_{n/2} in G (where n is the number of
                vertices of G) }
    Prove that HALF-HAMPATH is NP-complete.