[Rule] Knapsack to ClosestVectorProblem

[zazabap]

Source: Knapsack
Target: ClosestVectorProblem
Motivation: Embeds the Knapsack problem into a lattice structure, enabling solving via lattice reduction algorithms (LLL, BKZ). This is a classical reduction used in cryptanalysis of knapsack-based cryptosystems (Merkle–Hellman).
Reference: Lagarias & Odlyzko, "Solving Low-Density Subset Sum Problems", JACM 32(1), 1985

Reduction Algorithm

Notation:

• Source: $n$ items with weights $w_0, \ldots, w_{n-1}$, values $v_0, \ldots, v_{n-1}$, capacity $C$
• Target: CVP with lattice basis $B \in \mathbb{Z}^{(n+2) \times n}$ and target vector $\mathbf{t} \in \mathbb{Q}^{n+2}$

Lattice basis construction:

$$B = \begin{bmatrix} I_n \ \mathbf{w}^T \ \mathbf{v}^T \end{bmatrix} = \begin{bmatrix} 1 & 0 & \cdots & 0 \ 0 & 1 & \cdots & 0 \ \vdots & \vdots & \ddots & \vdots \ 0 & 0 & \cdots & 1 \ w_0 & w_1 & \cdots & w_{n-1} \ v_0 & v_1 & \cdots & v_{n-1} \end{bmatrix}$$

• Rows $0$ to $n-1$: identity matrix $I_n$ (enforces binary structure via target $\tfrac{1}{2}$)
• Row $n$: weight vector $\mathbf{w}$
• Row $n+1$: value vector $\mathbf{v}$

Target vector:

$$\mathbf{t} = \left(\tfrac{1}{2}, \tfrac{1}{2}, \ldots, \tfrac{1}{2}, C, V^*\right) \in \mathbb{Q}^{n+2}$$

where $V^*$ is the optimal Knapsack value (enumerate over candidate values or use binary search).

CVP problem: Find $\mathbf{x} \in \mathbb{Z}^n$ minimizing $|B\mathbf{x} - \mathbf{t}|^2$.

Why it works:

• The identity block produces residuals $(x_i - \tfrac{1}{2})^2$, which equal $\tfrac{1}{4}$ when $x_i \in {0, 1}$ and are larger otherwise — this encourages binary solutions.
• Row $n$ produces residual $(\sum w_i x_i - C)^2 = 0$ when the capacity constraint is tight.
• Row $n+1$ produces residual $(\sum v_i x_i - V^*)^2 = 0$ when the value is optimal.

Solution extraction: The CVP solution $\mathbf{x}$ directly gives the Knapsack selection vector.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
lattice_dimension	$n+2$
num_basis_vectors	$n$

Validation Method

Closed-loop testing: solve Knapsack by brute-force ($2^n$ enumeration), solve the reduced CVP, and verify that the closest lattice vector corresponds to the optimal Knapsack solution. Test with edge cases: all items fit, no items fit, items with equal value/weight ratios.

Example

Source instance: $n = 4$ items, capacity $C = 7$.

Item	Weight	Value
0	2	3
1	3	4
2	4	5
3	5	7

Brute-force optimal: select items ${0, 3}$, weight $= 7$, value $= 10$.

CVP formulation:

Basis $B$ (6×4):

	col 0	col 1	col 2	col 3
row 0	1	0	0	0
row 1	0	1	0	0
row 2	0	0	1	0
row 3	0	0	0	1
row 4	2	3	4	5
row 5	3	4	5	7

Target: $\mathbf{t} = (0.5,; 0.5,; 0.5,; 0.5,; 7,; 10)$

Verification (all 16 binary vectors):

$\mathbf{x}$	Weight	Value	$|B\mathbf{x} - \mathbf{t}|^2$	Feasible?
$(1,0,0,1)$	7	10	1.00	yes
$(0,1,1,0)$	7	9	2.00	yes
$(1,1,0,0)$	5	7	14.00	yes
$(0,0,1,1)$	9	12	9.00	no
$(1,0,0,0)$	2	3	75.00	yes

The optimal $\mathbf{x} = (1,0,0,1)$ achieves the minimum distance $|B\mathbf{x} - \mathbf{t}|^2 = 1.00$, correctly encoding the Knapsack optimum: items ${0, 3}$, value $= 10$.