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.)
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.
Hint: Reduce Hamiltonian Path to Traveling Salesperson.