## Description

- 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 A
^{0}A

P P

such that _{a}_{2}_{A}0 s(a) = _{a2A A}0 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 A^{0} A such that ^{P}_{a2A}_{0} 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 A^{0} A such that ^{P}_{a2A}_{0} s(a) B and ^{P}_{a2A}_{0} v(a) K?

- Prove PARTITION
_{p}SUBSET SUM.

- Prove SUBSET SUM
_{p}

- 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 w_{i}; x_{j}; y_{k}; z_{l}, 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 w
_{e}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