  We show NP-hardness of a generalized quadratic programming problem, which we
called Unconstrained N-ary Quadratic Programming (UNQP). This problem has
recently become practically relevant in the context of novel memristor-based
neuromorphic microchip designs, where solving the UNQP is a key operation for
on-chip training of the neural network implemented on the chip. UNQP is the
problem of finding a vector $\mathbf{v} \in S^N$ which minimizes
$\mathbf{v}^T\,Q\,\mathbf{v} +\mathbf{v}^T \mathbf{c} $, where $S = \{s_1,
\ldots, s_n\} \subset \mathbb{Z}$ is a given set of eligible parameters for
$\mathbf{v}$, $Q \in \mathbb{Z}^{N \times N}$ is positive semi-definite, and
$\mathbf{c} \in \mathbb{Z}^{N}$. In memristor-based neuromorphic hardware, $S$
is physically given by a finite (and small) number of possible memristor
states. The proof of NP-hardness is by reduction from the Unconstrained Binary
Quadratic Programming problem, which is a special case of UNQP where $S = \{0,
1\}$ and which is known to be NP-hard.
