Verification gap

P vs NP: NP problems have solutions that are quick to check; P problems are quick to solve. Unproven whether they're equal; most bet not. The gym approach exploits this gap. The model writes the checker (the reward), and search does the generating. A loose analogy, since physical control isn't formally an NP problem. Ties to Turing-complete universe: even if everything can be expressed as code, P ≠ NP would mean not everything can be found efficiently. That's the tractability wall, stated precisely.

Parallel (Sam): direct control vs building the verifier around it (did you fall, and what inputs came before the failure). The RL policy is the bridge: it codifies physics into one action but doesn't generalize (a bike policy can't cut a steak). Complexity-theory equivalents: (1) the policy is like a stored certificate, or better, a solver that bakes in search for one family of problems; (2) non-uniform vs uniform computation: P/poly allows a separate hand-built circuit per input size, like one policy per task, versus one algorithm for everything; (3) NP-completeness and reductions: solve one hard problem efficiently and you can turn every other one into it. That's the generalist-robot-brain dream. Open question: what plays the role of a reduction between physical tasks?