  Linear and semidefinite programming (LP, SDP), regularisation through basis
pursuit (BP) and Lasso have seen great success in mathematics, statistics, data
science, computer-assisted proofs and learning. The success of LP is
traditionally attributed to the fact that it is "in P" for rational inputs. On
the other hand, in his list of problems for the 21st century S. Smale calls for
"[Computational] models which process approximate inputs and which permit
round-off computations". Indeed, since e.g. the exponential function does not
have an exact representation or floating-point arithmetic approximates every
rational number that is not in base-2, inexact input is a daily encounter. The
model allowing inaccurate input of arbitrary precision, which we call the
extended model, leads to extended versions of fundamental problems such as:
"Are LP and other aforementioned problems in P?" The same question can be asked
for an extended version of Smale's 9th problem on the list of mathematical
problems for the 21st century: "Is there a polynomial time algorithm over the
real numbers which decides the feasibility of the linear system of
inequalities, and if so, outputs a feasible candidate?" One can thus pose this
problem in the extended model. Similarly, the optimisation problems BP, SDP and
Lasso, where the task is to output a solution to a specified precision, can
likewise be posed in the extended model, also considering randomised
algorithms. We will collectively refer to these problems as the extended
Smale's 9th problem, which we settle in both the negative and the positive
yielding two surprises: (1) In mathematics, sparse regularisation, statistics,
and learning, one successfully computes with non-computable functions. (2) In
order to mathematically characterise this phenomenon, one needs an intricate
complexity theory for, seemingly paradoxically, non-computable functions.
