The Knapsack Problem ( KP ) gives you a target integer t and an array data with

Question

The Knapsack Problem (KP) gives you a target integer t and an array data with n positive integers, and it returns the subset of data with a sum as close
as possible to t without going over.

The Knapsack Size Problem (KSP) gives you a target integer t and an array data with n positive integers, and it returns the largest integer less than t that
some subset of data sums up to.

The Full Knapsack Problem (FKP) gives you a target integer t and an array data with n positive integers, and it returns true if there is a subset of data
that sums to exactly t and false otherwise.

1. Prove that FKP NP by giving pseudocode for a polynomial-time verification algorithm for FKP.

2. What kind of reduction do you need between FKP and KSP in order to prove that KSP P if FKP P? Justify your answer.

Explanation / Answer

1. Let us define some of the terms will be used for the algorithm.

Let X is set of problems that can be solved in polynomial time and let NP is a set of problems for which a solution can be verified in polynomial time.

NP abbreviation is Nondeterministic Polynomial time.

Two important things to remember before we write an algorithm for polynomial-time verification:

A problem X can be reduced to another problem Y if any instance of X can be rephrased to an instance of Y, the solution to which provides a solution to the instance of X, This method is called as a transformation.

Pseudocode for a polynomial-time verification algorithm for FKP.

2. Let X is set of problems that can be solved in polynomial time and let NP is a set of problems for which a solution can be verified in polynomial time.

If X p Y and X is NP-Complete, Y is also NP-Complete/

So how can we reduce problem X to problem Y?

We need to have Transform instances of X to instances of Y in polynomial time s.t. Y: “yes” iff X: “yes”

Every problem X NP p Y, then Y is NP-Hard.

Y is NP-Hard and Y NP, then Y is NP-Complete.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.