===========================================================================
CSC 363                    Homework Assignment 3                Winter 2008
===========================================================================

Due: April 11 in tutorial

For each question, please write up your answer 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 if P = NP then it is possible to factor numbers in polynomial 
time. In other words, on input n > 1 that is not a prime, it is possible to 
compute two numbers p, q > 1 such that p * q = n.

2. Consider the LargeSum problem: 

   LargeSum = {<S, t,b > | S is a subset of positive integers, and t > b
               are positive integers, and there is a subset of S that sums 
               to a number c such that b <= c <= t}

  a. show that LargeSum is NP-complete.

  b. show a polynomial time reduction from LargeSum to SubsetSum.
     NOTE: You may not use the generic reduction into SAT and then to 
     SUBSETSUM for your answer. You should find a direct reduction.

     HINT: Assume first that t-b is a power of 2. What items would be good 
           to add to a LargeSum instance when reducting it to SubsetSum?
           

3. The Traveling Salesman Problem an agent wishes to make a tour,
visiting each city exactly once and finishing at the city she starts from.
There is an integer cost c(i,j) to travel from city i to city j, and the 
goal is to make the tour whose total cost is minimum, where the cost 
associated with a tour is the sum of the individual costs along the edges 
of the tour.

The formal language corresponding to the problem is
TSP = {<G,c,k> | G is the complete graph, c is the cost function, assigning
each edge an integer number, k is an integer, and G has a tour with cost at
most k}.

The optimization problem version is finding the minimal cost of a tour
associated with a graph G and cost function c.

(i) Prove that TSP is NP-complete.
(ii) Show that the optimization problem version is NP-hard.
(iii) Show that the optimization problem version of TSP is
        self-reducible (i.e., if we can solve it, we can also find a tour
         with minimum cost.

In your answer you may use the fact that HAM-CYCLE is NP complete.

4. Pick one of the NP-complete problems discussed in class and show that 
it can be solved in linear space.