Theorems 1–3 and §4 (reduction): subset sum is solvable iff $0$ is not a local min of $x^{\mathsf T}Mx$ on $x\ge0$, iff $M$ is not copositive, iff …

Let $d_0; d_1, \dots, d_n$ be positive integers, the data of a subset sum instance, and let $l$ be the total number of decimal digits in these data. Let $\delta$ be an integer and $\varepsilon$ a rational number with

Let $M$ be the symmetric $2n \times 2n$ matrix of the quadratic form $f_5$ in the variables $(y, s)$, and $Q(x) = x^{\mathsf T}Mx$. The following are equivalent:

1. the subset sum instance is solvable (some subset of $\{d_1, \dots, d_n\}$ sums to $d_0$);
2. $x = 0$ is not a local minimum of $Q$ on $\{x \ge 0\}$ (Problem 1);
3. $Q$ is not bounded below on $\{x \ge 0\}$ (Problem 2);
4. there is $x \ge 0$ with $Q(x) < 0$ (Problem 3);
5. $M$ is not copositive;
6. there is $x \ge 0$ with $e^{\mathsf T}x = n$ and $Q(x) < 0$ (Problem 4 with $a_0 = n$);
7. $u = 0$ is not a local minimum of $h(u) = (u^2)^{\mathsf T} M (u^2)$ on $\mathbb R^{2n}$ (Problem 11);
8. $h$ is not bounded below on $\mathbb R^{2n}$ (Problem 12).

This is the mathematical content of the paper's Theorems 1–3 and §4: the explicit map from $(d_0; d_1, \dots, d_n)$ to $M$ is a reduction from subset sum to each of these questions, so each of them is NP-hard; in particular deciding whether a feasible point of a quadratic program is a local minimum, and deciding copositivity, are NP-hard.

Formalization Note Only the correctness of the reduction is formalized. Not formalized: membership in NP (Lemma 1), the polynomial-time computability of $M$ from the data, the encoding size of $M$, and the NP-completeness of subset sum (cited in the paper from Garey–Johnson). $M$ has rational entries ($\varepsilon$ is rational and $(d_0^2 - n\delta)/n^2$ need not be an integer); a positive integer multiple of it is the integer matrix of Theorem 3, has the same answer to every question in the list, and this rescaling is not formalized. The paper's §3 standing assumption "$D$ is not PSD" is not imposed ($M$ can be PSD, e.g. $n = 1$, $d_1 = 5$, $d_0 = 1$), and the equivalence holds without it. The bound on $\varepsilon$ is written $\varepsilon \cdot 2^{nl^2} < 1$ in $\mathbb Q$; $l$ counts decimal digits. For $n = 0$ all eight statements are false, so no hypothesis $n \ge 1$ is needed.