# A proof that Exponential RSI is impossible — retained record

> Retained reddit record from reddit:cscareerquestions.

Canonical: https://highsignal.app/data/records/ca22ebd7359e230f

[← sources](https://highsignal.app/data)


source: [reddit](https://highsignal.app/data/reddit) (reddit:cscareerquestions)  published 2026-11-13 16:43 ingested 2026-11-14 02:36

[original source ↗](https://www.reddit.com/r/cscareerquestions/comments/1xvcsh6/a_proof_that_exponential_rsi_is_impossible/)

## retained text



```
My own proof ran through fable 5.2 to clean up and double check

\*\*Corollary (meta-search over approaches).\*\* Everything above assumes the approach is already chosen. Let \`A\` be the number of candidate approaches (formulations, representations, proof strategies), of which a negligible fraction work.

\- \*Routine problems:\* \`A = O(n)\`. There is a short list of known ways to attack the problem. Total cost is \`O(n · b\^d)\`.

\- \*Open problems:\* an approach is itself a description of length \`L\` built from \`a\` choices per position, so \`A = a\^L\`. Total cost is \`Θ(a\^L · b\^d)\`.

\*Proof.\* With no prior over approaches, the expected number tried before reaching a working one is \`Θ(A)\`. Each approach costs up to \`b\^d\` attempts to exhaust or abandon. Multiply. ∎

In the notation where the inner search is \`O(m\^k)\`, this is \`O(m\^k · A)\`, with \`A\` linear for routine problems and exponential for open ones.

\*\*Consequence.\*\* Setting \`a\^L · b\^d = C\` gives

\`d ≈ (log C − L·log a) / log b\`

The meta-search is paid for out of the same budget before any depth is gained. Returns are still logarithmic, with a fixed overhead that grows with how unconstrained the problem is.

\*\*Note.\*\* A failed approach can't be recognized as failed without exhausting it, so in practice each approach gets a capped budget and the caps are raised in rounds. This costs only a constant factor.
```



document fetched 2026-11-14 00:23 · canonical https://reddit.com/r/cscareerquestions/comments/1xvcsh6/a_proof_that_exponential_rsi_is_impossible
