===========================================================================
CSC 363H                        Exercise 8                        Fall 2007
===========================================================================

A.  Recall the following language.

        PATH = { <G,s,t> : G is an undirected graph that contains
                a path from s to t }

    (a) Show that PATH is NP-complete iff P = NP.

    (b) Show that PATH <=p SUBSET-SUM.
        Does this mean that P = NP?  Justify.

B.  Show that the language 363SUM (defined below) is NP-complete.

        363SUM = { <S> : S = {z_1,z_2,...,z_n} is a set of integers
                such that there is some subset S' of S whose sum is
                exactly 363 -- SUM_{z in S'} z = 363 }