CS4123 Theory of Computation. A99
Homework 4

Prof. Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute


Homework 4

Due on Monday, October 11, 1999 at the beginning of class (9:00 p.m.)

Problems:

  1. Multiprocessor Scheduling Show that the Multiprocessor Scheduling problem is NP-complete.

    Hint: Reduce Subset-Sum to Multiprocessor Scheduling.

     Try making the reduction into 2 steps:
    
    (1) Show that the PARTITION problem is NP-Complete
        
        where:
    
        The partition problem is defined as follows:
    
        GIVEN: A multiset (i.e. a set in which repetition
               of elements is allowed) of positive integers 
               {x_1,...,x_k}
    
        ANSWER: "YES" if there is a subset {y_1,...,y_l}
        of {x_1,...,x_k} such that 
        y_1 + ... + y_l = 1/2 * (x_1 + .... + x_k).
        In other words, the multiset can be split into
        two parts, each one summing up to half the sum
        of all elements in the multiset.        
    
        (1.1) Show that PARTITION belongs to NP.
        (1.2) Show that SUBSET-SUM <=p PARTITION
              Hint: Construct the polynomial time
              transformation between the two problems
              "inspired" in the following example:
    
              ({1,6,11}, 7) belongs to SUBSET-SUM
              if and only if
              ({2,12,22},14) belongs to SUBSET-SUB
              if and only if
              {2,12,22,8} belongs to PARTITION, i.e.
              it can be split into two parts 
              having the same sum (namely, {2,12,8}
              and {22}). Note that 
              8 = |(2+12+22) - (2*14)|
              
    (2) PARTITION <=p MULTI-PROCESSOR
        (this part is fairly easy.)
    
    

  2. 3Color
    Consider the 3Color problem described in problem 7.34. Show that the 3Color problem is NP-complete. (You don't need to show that the problem is in NP, since we already proved it in homework 3).

    Hint: Reduce 3SAT to 3Color, i.e. show that 3SAT <=p 3Color:

    
     Given an input to 3SAT, i.e. a formula in conjunctive
     normal form (or a "3 layer logic circuit") C, construct
     a graph G such that: 
      
       there is an assignment of values to the variables in C 
       that makes the circuit to output 1 
       IF AND ONLY IF 
       there is a 3coloring of the graph G.
    
     In order to achieve this, follow the steps below:
    
     (1) Provide a word description of how to construct G
         given C using the following example as "inspiration":
         (see Hint in problem 7.34 of the textbook) 
    
         C:  ( x or ~y or z) and (z or t or ~z)
    
         G:
                                             ---------------------
                                            |                     | 
           ----- v11   ------ v14          v21   ------ v24       |
          |     /   \  |     /   \        /   \  |     /   \      |
          |    /     \ |    /     \      /     \ |    /     \     |
          |   v12----v13   v15----v16   v22----v23   v25----v26   |
          |    |            |       \    |            |      |    |
          |    |            |        \   |            |      |    |
          |    |             ------   \  |       -------------    |
          |    |                   |   \ |      |     |           |
          |    x --- ~x     y --- ~y     z --- ~z     t --- ~t    |
          |    |      |     |      |     |      |     |      |    |
          |    |      |     |      |     |      |     |      |    |
          |     ---------------------------------------------     |
          |                           |                           |
          |                           R                           |
          |                         /   \                         |
          |                        0 --- 1                        |
          |                       / \                             |
           -----------------------   -----------------------------
    
          Think of 0, 1, R as the 3 colors available to color the graph.
    
      (2) Show that G can be constructed in polynomial time in the
          size of C.
    
      (3) Show that there is a way to 3color the resulting graph G
          IF AND ONLY IF at least one of the literals in each clause
          is assigned color/value 1. 
    

  3. Traveling Salesperson Show that the Traveling Salesperson problem is NP-complete. (You don't need to show that the problem is in NP, since we already proved it in homework 3).

    Hint: Reduce Hamiltonian Path to Traveling Salesperson.

Additional Problems for students taking this course for graduate credit:

  1. Problem 7.17 from the textbook.