# The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learning

arXiv: https://arxiv.org/abs/2110.15734 · HTML: https://mlsanity.com/paper/2110.15734/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2021.

## Built on by (most cited first, 12 of 12)

- [Limitations of Deep Learning for Inverse Problems on Digital Hardware](https://mlsanity.com/paper/2202.13490/) (2022)
- [On the consistent reasoning paradox of intelligence and optimal trust in AI: The power of 'I don't know'](https://mlsanity.com/paper/2408.02357/) (2024)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [A phase transition for finding needles in nonlinear haystacks with LASSO artificial neural networks](https://mlsanity.com/paper/2201.08652/) (2022)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations](https://mlsanity.com/paper/2309.01796/) (2023)
- [When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation](https://mlsanity.com/paper/2312.11425/) (2023)
- [Do stable neural networks exist for classification problems? -- A new view on stability in AI](https://mlsanity.com/paper/2401.07874/) (2024)
- [Mathematical Algorithm Design for Deep Learning under Societal and Judicial Constraints: The Algorithmic Transparency Requirement](https://mlsanity.com/paper/2401.10310/) (2024)
- [Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization](https://mlsanity.com/paper/2408.06212/) (2024)
- [When fractional quasi p-norms concentrate](https://mlsanity.com/paper/2505.19635/) (2025)
- [Navier-Stokes lost in translation: Why Lean verification of AI autoformalisation does not guarantee correct natural language proofs](https://mlsanity.com/paper/2610.08144/) (2026)

## Abstract (arXiv)

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.