Prove that the Knapsack Problem (Problem 13.4, Page 550) is in NP.

See Example 13.1 (Page 556) for the (partial) solution to a similar problem.

[It would be a complete (rather than partial) solution if they had simply

computed the complexity of their 'second phase', and observed that the

complexity was bounded by a polynomial.] Exercise 13.4(b), another similar

problem, is solved in detail in the lecture notes.

Note that your algorithm only is supposed to CHECK a proposed solution,

not FIND a solution! Remember to refer to the 'checklist' in the notes and

do all FOUR things necessary to show a problem belongs to NP. The notes say:

To show a problem belongs to NP, you must do four things:

1) describe the encoding used for the instance

2) describe the encoding used for the certificate

3) describe the algorithm that will check if the certificate is a valid solution

4) analyze the time complexity of that algorithm.

If the complexity is (bounded by) some polynomial of the input size,

then the problem is indeed in NP.

550 Chapter 13 NP-Complete Problems Problem 13.2 Job scheduling with penalties Suppose there are n jobs Ji,.. . , J to be executed one at a time. We are given execution times t. . 'n, deadlines di,... , dn (measured from the starting time of the first job executed), and penalties for missing the deadlines pi,... . Pa. Assume the execution times deadlines, and penalties are all positive integers. A schedule for the jobs is a permutation t of (1,2,..., n), where Jxe) is the job done first, Jr2) is the job done next, and so on. For a particular schedule, the penalty for the jth job is denoted as P,, and is defined as P-Pu) if job Jcompletes after the deadline dr, otherwise P 0. The total penalty for a particular schedule is Optimization Problem: Determine the minimum possible penalty (and find an optimal schedule-one that minimizes the total penalty) Decision Problem: Given, in addition to the inputs described, a nonnegative integer k, is there is a schedule with Pi 3k? n Problem 13.3 Bin packing Suppose we have an unlimited number of bins each of capacity one, and n objects with sizes si,.. , sn where 0