For each of the two questions below, decide whether the answer is (i) \Yes," (ii)\No," or (iii) \Unknown, because it would resolve the question of whether P = NP." Give a brief explanation of your answer.
Let's de ne the decision version of the Interval Scheduling Problem from Chapter 4 as follows: Given a collection of intervals on a time-line, and a bound k, does the collection
contain a subset of nonoverlapping intervals of size at least k? Question: Is it the case that Interval Scheduling P Vertex Cover?
Question: Is it the case that Independent Set P Interval Scheduling?
PARTITION : Given a nite set A and a size s(a) 2 Z for each a 2 A, is there a subset A0 A
P P
such that a2A0 s(a) = a2A A0 s(a) ?
SUBSET SUM : Given a nite set A, a size s(a) 2 Z for each a 2 A and an integer B, is there a subset A0 A such that Pa2A0 s(a) = B?
KNAPSACK : Given a nite set A, a size s(a) 2 Z and a value v(a) 2 Z for each a 2 A and integers B and K, is there a subset A0 A such that Pa2A0 s(a) B and Pa2A0 v(a) K?
Prove PARTITION p SUBSET SUM.
Prove SUBSET SUM p KNAPSACK.
Since the 3-Dimensional Matching Problem is NP-complete, it is natural to expect that the cor-responding 4-Dimensional Matching Problem is at least as hard. Let us de ne 4-Dimensional
Matching as follows. Given sets W, X, Y, and Z, each of size n, and a collection C of ordered 4-tuples of the form wi; xj; yk; zl, do there exist n 4-tuples from C so that no two have an element in common?
Prove that 4-Dimensional Matching is NP-complete.
You are given a directed graph G = (V, E) with weights we on its edges e 2 E. The weights can be negative or positive. The Zero-Weight-Cycle Problem is to decide if there is a simple cycle in G so that the sum of the edge weights on this cycle is exactly 0.
Prove that this problem is NP-complete.
1
