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