← sources

A proof that Exponential RSI is impossible

source: reddit (reddit:cscareerquestions)published 2026-11-13 16:43ingested 2026-11-14 02:36

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