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

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 elementof 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 elementof 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:

If all problems Z NP are reducible to X, then X is NP Hard.

X is NP-Complete if X is NP-Hard and X NP.

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 provide a solution to the instance of X’’, This method is known as a transformation.

Pseudo code for a polynomial-time verification algorithm for FKP:

Choose a known NP-Complete problem X.

Reduce problem X to problem Y

Describe a transformation that maps instances of X to instances of Y.

Prove the transformation works.

Prove the transformation runs in polynomial time.

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.