127 Complexity — Subset Sum To Partition
127.1 Overview
This file states the Subset Sum and Partition decision problems over a finite type \(U\) with weights in \(\mathbb {N}\), and formalises the classical many-one reduction from Subset Sum to Partition obtained by adjoining two dummy items of weights \(2W - T\) and \(W + T\), where \(W = \sum _{a} w(a)\) is the total weight. Completeness, soundness, and the resulting equivalence are proved under the hypothesis \(T \le W\), which is needed because subtraction on \(\mathbb {N}\) truncates at \(0\).
127.2 Declarations
Given a weight function \(w : U \to \mathbb {N}\) on a finite type \(U\) and a target \(T \in \mathbb {N}\), the predicate asserts that some subset \(S \subseteq U\) has total weight exactly \(T\), i.e. \(\exists S,\ \sum _{a \in S} w(a) = T\).
Given a weight function \(v : U \to \mathbb {N}\) on a finite type \(U\), the predicate asserts that some subset \(S \subseteq U\) has the same total weight as its complement, i.e. \(\exists S,\ \sum _{b \in S} v(b) = \sum _{b \in S^{c}} v(b)\).
The weight function on the augmented universe \(U \oplus \mathrm{Bool}\) built from a Subset Sum instance \((w, T)\). Writing \(W = \sum _{a} w(a)\), it sends the original item \(\mathrm{inl}\, a\) to \(w(a)\), the first dummy item \(\mathrm{inr}\, \mathsf{true}\) to \(2W - T\), and the second dummy item \(\mathrm{inr}\, \mathsf{false}\) to \(W + T\).
Let \(w : U \to \mathbb {N}\) be a weight function on a finite type \(U\), and let \(T \in \mathbb {N}\) satisfy \(T \le \sum _{a} w(a)\). If the Subset Sum instance \((w, T)\) has a solution — some subset of \(U\) with total weight exactly \(T\) — then the Partition instance on the augmented type \(U \oplus \mathrm{Bool}\) whose weights are given by the reduction weight function built from \((w, T)\) has a solution; that is, \(U \oplus \mathrm{Bool}\) admits a subset whose total weight equals that of its complement.
Let \(w : \mathbb {N}^{U}\) be a weight function on a finite type \(U\), and let \(T \in \mathbb {N}\) be a target with \(T \le \sum _{a} w(a)\). Form the reduction weight function on the augmented type \(U \oplus \mathrm{Bool}\), which assigns each original item the weight \(w(a)\), the first dummy item the weight \(2\sum _a w(a) - T\), and the second dummy item the weight \(\sum _a w(a) + T\). Then, if this augmented instance is a yes-instance of Partition — some subset of \(U \oplus \mathrm{Bool}\) has the same total weight as its complement — the original instance \((w, T)\) is a yes-instance of Subset Sum, i.e. some subset of \(U\) has total weight exactly \(T\).
Let \(U\) be a finite type, let \(w : U \to \mathbb {N}\) be a weight function, and let \(T \in \mathbb {N}\) be a target satisfying \(T \le \sum _{a} w(a)\). Write \(W = \sum _{a} w(a)\), and form the weight function on the augmented universe \(U \oplus \mathrm{Bool}\) that assigns weight \(w(a)\) to each original item \(a\), weight \(2W - T\) to one added dummy item, and weight \(W + T\) to a second added dummy item. Then some subset of \(U\) has total \(w\)-weight exactly \(T\) if and only if the augmented universe admits a partition into two parts of equal total weight.