  Hardness of approximation (HA) -- the phenomenon that, assuming P $\neq$ NP,
one can easily compute an $\epsilon$-approximation to the solution of a
discrete computational problem for $\epsilon > \epsilon_0 > 0$, but for
$\epsilon < \epsilon_0$ it suddenly becomes intractable -- is a core phenomenon
in the foundations of computations that has transformed computer science. In
this paper we study the newly discovered phenomenon in the foundations of
computational mathematics: generalised hardness of approximation (GHA) -- which
in spirit is close to classical HA in computer science. However, GHA is
typically independent of the P vs. NP question in many cases. Thus, it requires
a new mathematical framework that we initiate in this paper. We demonstrate the
hitherto undiscovered phenomenon that GHA happens when using AI techniques in
order to train optimal neural networks (NNs). In particular, for any non-zero
underdetermined linear problem the following phase transition may occur: One
can prove the existence of optimal NNs for solving the problem but they can
only be computed to a certain accuracy $\epsilon_0 > 0$. Below the
approximation threshold $\epsilon_0$ -- not only does it become intractable to
compute the NN -- it becomes impossible regardless of computing power, and no
randomised algorithm can solve the problem with probability better than 1/2. In
other cases, despite the existence of a stable optimal NN, any attempts of
computing it below the approximation threshold $\epsilon_0$ will yield an
unstable NN. Our results use and extend the current mathematical framework of
the Solvability Complexity Index (SCI) hierarchy and facilitate a program for
detecting the GHA phenomenon throughout computational mathematics and AI.
