Knapsack-search is NP

Statement

Lemma

Knapsack-search is in NP.

Proof

The problem statement is in the form of a search problem.

Given a proposed solution to check if it solves the problem we just need to calculate and check the following.

This takes time, so is polynomial.

This makes Knapsack-search run in polynomial time.