[2022] COMP 3170 Assignment 5 - NP-Complete
COMP 3170 Assignment 5
All problems are written problems. Solutions can be prepared however you like, though they must be legible (marks may be deducted if not). Solutions should be submitted only on Crowdmark. The assignment is out of 27 marks. See course information for guidelines on academic integrity.
[8 marks]
Problem 1 Consider the following problem 4SUM:
Given a set S, is there a subset {x, y, z, w} ⊂ S so that x + y + z + w = 0?
Show that 4SUM is 3SUM-Hard. More precisely, define a reduction f from 3SUM to 4SUM and show that it (i) runs in o(n2) time and (ii) is a valid reduction.
[5 + 14 marks]
Problem 2 Recall the partition problem that we saw in class. We will show that the partition problem is NP-Complete.
(a) Show that the partition problem is in NP by defining certificates for the partition problem and describing a verification algorithm for these certificates. You should show that your algorithm takes polynomial time and is, indeed, a verification algorithm.
(b) Consider a variant of the subset sum problem called the positive subset sum problem, in which all elements of the set S and the target k are all positive integers. You may assume without proof that the positive subset sum problem is NP-Complete (in fact, our proof from class that subset sum is NP-Complete also shows this). Show that the partition problem is NP-Hard by describing a polynomial time reduction from positive subset sum to partition. You should describe how to transform an instance of positive subset sum into an instance of partition, show that the reduction takes polynomial time, and show that the reduction is valid.
