Homework 6 (NP and Computational Intractability) Solution

$30.00

Category:

Description

  1. 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?

 

 

 

  1. 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

 

 

 

  1. 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.

 

 

 

  1. 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


error: Content is protected !!