In his 9th problem on the list of problems for the 21st century, S. Smale asks whether there exist polynomial-time algorithms over the reals for Linear Programming (LP). He also highlights the issue of extending traditional exact computational models to allow for inexact representation.

Extending Smale's 9th question to inexact arithmetic leads to a surprising conclusion: even on well-conditioned problem spaces, implementable algorithms cannot approximate minimizers for LP or Basis Pursuit (BP).

And yet, randomization completely changes the picture: randomized algorithms can compute minimizers with arbitrarily high probability, despite deterministic non-computability. This behavior contrasts sharply with the established wisdom that randomness cannot aid computability beyond a success probability of \(1/2\), dating back to the work of de Leeuw, Moore, Shannon, and Shapiro from 1956.

More precisely, using the Solvability Complexity Index hierarchy, we construct both rational and real versions of problem spaces \(\Omega_{K,p}\) (with any \(K \in \mathbb{N}\) and \(p \in (0,1)\) --- in particular, \(p\) can be chosen to be arbitrarily close to \(1\)) for LP and BP on which no deterministic inexact-arithmetic algorithm can compute \(K\) digits of minimizers. However, on \(\Omega_{K,p}\), there exist randomized algorithms that compute \(K\) digits with probability \(p\).

Furthermore, the problem spaces \(\Omega_{K,p}\) exhibit several phase transitions. Allowing partial or non-halting algorithms increases achievable success probabilities. Meanwhile, on \(\Omega_{K,p}\), deterministic algorithms with unbounded complexity recover \(K-1\) digits and polynomial-time algorithms recover \(K-2\) digits.

More general results bound the condition numbers and norms of inputs in \(\Omega_{K,p}\) by \(O(10^{-K}/(1-p))\), suggesting a trade-off between condition numbers, precision, and effectiveness of randomization in the form of "The more poorly conditioned or the higher the desired precision, the more randomness can help".