Establishing lower bounds for Ramsey numbers is a classical family of hard combinatorial feasibility problems: one seeks a 2-coloring of the edges of $K_n$ avoiding a red $K_r$ and a blue $K_s$. Such witnesses have accumulated over decades through problem-specific discrete heuristics, with several key values remaining out of reach for generic methods. We replace direct search in graph space by continuous optimization on a hypercube relaxation, retaining binary structure through the oracle, the rounding, and a final exact verification.

Counting forbidden monochromatic cliques by a pseudo-Boolean polynomial $M(x)$ turns satisfiability into the minimization of a smooth multilinear objective over the unit hypercube $[0,1]^m$; since $M$ is affine in each coordinate, its continuous and integral minima coincide. The vanilla Frank-Wolfe method performs surprisingly well on this relaxation, even though the objective is non-monotone supermodular and only stationarity guarantees apply: its linear minimization oracle over the hypercube is available in closed form and returns a binary vertex at every step, anchoring the fractional iterates to concrete candidate colorings, and a conditional-expectations rounding then converts any iterate to a binary one without increasing the violation count.

This projection-free pipeline recovers a significant portion of the known lower-bound table and, most notably, reliably finds $42$-vertex graphs certifying $R(5,5) \geq 43$ — a long-standing benchmark that recent LLM-driven evolutionary search (AlphaEvolve, Nagda et al., 2026) does not report. We discuss the resulting multimodal solution landscape and the central open question: why Frank-Wolfe succeeds so well on a non-monotone supermodular objective for which no approximation guarantee is known.

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".