  Given a neural network, training data, and a threshold, it was known that it
is NP-hard to find weights for the neural network such that the total error is
below the threshold. We determine the algorithmic complexity of this
fundamental problem precisely, by showing that it is ER-complete. This means
that the problem is equivalent, up to polynomial-time reductions, to deciding
whether a system of polynomial equations and inequalities with integer
coefficients and real unknowns has a solution. If, as widely expected, ER is
strictly larger than NP, our work implies that the problem of training neural
networks is not even in NP.
