We are going to prove that the Knapsack-search is NP-complete . We will do this using the 3-SAT but first going through the Subset-sum problem .

# Subset-sum problem

Statement

This can be solves using Dynamic Programming in a similar way to the Knapsack problem in $O(nt)$. However, similar to the Knapsack problem this is not a polynomial time algorithm in the length of the input as that is $n\log_2(t)$. Therefore it is Pseudo-polynomial .

Subset-sum problem is in NP

Moreover it is NP-complete .

Subset-sum problem is NP-complete

# Knapsack problem

This subset-sum problem is very similar to the Knapsack-search problem so we have the following.

Knapsack-search is NP-complete