## Introduction

The knapsack problem is a quintessential example of an NP-complete problem in computer science and combinatorial optimization. Understanding why it is NP-complete provides important insight into the nature of computational hardness and helps explain why certain optimization problems resist efficient solutions. This article breaks down the proof step by step.

## The Knapsack Problem

The 0/1 knapsack problem involves a set of `$n$` items, each with a weight and a value, and a knapsack with a maximum weight capacity. The goal is to select a subset of items that maximizes total value without exceeding the weight capacity.

### Formal Definition

- **Values**: `$v = \{v_1, v_2, \ldots, v_n\}$`
- **Weights**: `$w = \{w_1, w_2, \ldots, w_n\}$`
- **Capacity**: `$W$`
- **Decision variables**: `$x_i \in \{0, 1\}$` (include item `$i$` or not)

The optimization version maximizes:

`$$\sum_{i=1}^{n} v_i x_i$$`

subject to:

`$$\sum_{i=1}^{n} w_i x_i \leq W$$`

For the NP-completeness proof, we use the **decision version**: given a target value `$V$`, does there exist a subset of items with total weight at most `$W$` and total value at least `$V$`?

## What Does NP-Complete Mean?

A problem is NP-complete if it satisfies two conditions:

1. **It is in NP**: Given a proposed solution, you can verify whether it is correct in polynomial time.
2. **It is NP-hard**: Every problem in NP can be reduced to it in polynomial time.

### Step 1: Knapsack Is in NP

Given a candidate solution (a subset of items), verification is straightforward:

- Sum the weights of the selected items: `$O(n)$` operations
- Check that the total weight does not exceed `$W$`
- Sum the values: `$O(n)$` operations
- Check that the total value is at least `$V$`

All of this runs in `$O(n)$` time, which is polynomial. So the knapsack decision problem is in NP.

### Step 2: Knapsack Is NP-Hard (via Reduction from Subset Sum)

The Subset Sum problem is a known NP-complete problem: given a set of integers `$S = \{s_1, s_2, \ldots, s_n\}$` and a target `$T$`, does any subset of `$S$` sum to exactly `$T$`?

We reduce Subset Sum to Knapsack in polynomial time:

1. For each integer `$s_i$` in the Subset Sum instance, create a knapsack item with weight `$w_i = s_i$` and value `$v_i = s_i$`.
2. Set the knapsack capacity `$W = T$`.
3. Set the target value `$V = T$`.

Now, a subset with total weight at most `$T$` and total value at least `$T$` exists if and only if there is a subset summing to exactly `$T$`. This reduction runs in `$O(n)$` time (linear in the number of items).

Since Subset Sum is NP-complete and it reduces to Knapsack in polynomial time, Knapsack is NP-hard. Combined with Step 1, Knapsack is NP-complete.

## Example

| Item | Weight (`$w$`) | Value (`$v$`) |
| --- | --- | --- |
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
| 4 | 5 | 6 |

**Capacity**: `$W = 7$`

### Brute Force Approach

Evaluate all `$2^4 = 16$` subsets:

- Items {1, 2}: weight = 5, value = 7. Fits.
- Items {1, 3}: weight = 6, value = 8. Fits.
- Items {2, 3}: weight = 7, value = 9. Fits (at capacity).
- Items {1, 2, 3}: weight = 9 > 7. Does not fit.

The optimal solution is items {2, 3} with value 9.

## Why Dynamic Programming Does Not Disprove NP-Completeness

Dynamic programming solves the knapsack problem in `$O(nW)$` time. This looks polynomial, but it is actually **pseudo-polynomial**. The key distinction is that the input size of `$W$` is `$\log_2(W)$` bits, not `$W$` itself. So `$O(nW)$` is exponential in the number of bits needed to represent `$W$`.

For example, if `$W = 2^{40}$`, representing it requires only 40 bits, but the DP table has over a trillion entries. This is why the DP approach does not place knapsack in P.

## Complexity Summary

| Algorithm | Time Complexity | Notes |
| --- | --- | --- |
| Brute force | `$O(2^n)$` | Evaluates all subsets |
| Dynamic programming | `$O(nW)$` | Pseudo-polynomial (exponential in input size) |
| Branch and bound | Varies | Practical but worst case still exponential |
| FPTAS | `$O(n^2 / \epsilon)$` | Fully polynomial-time approximation scheme |

## Key Takeaways

- The knapsack problem is NP-complete because it is in NP (solutions are verifiable in polynomial time) and NP-hard (Subset Sum reduces to it).
- The `$O(nW)$` dynamic programming solution is pseudo-polynomial, not truly polynomial, because `$W$` can be exponentially large relative to the number of input bits.
- Despite being NP-complete, practical instances of the knapsack problem are often solvable efficiently using DP, branch and bound, or approximation algorithms. NP-completeness describes worst-case hardness, not typical-case difficulty.
- Understanding this distinction between polynomial and pseudo-polynomial time is fundamental to computational complexity theory and has practical implications for algorithm design.