Eliezer Yudkowsky has, on several occasions, claimed that AI’s success at protein folding was essentially predictable. His reasoning (e.g., here) is straightforward and convincing: proteins in our universe fold reliably; evolution has repeatedly found foldable and functional sequences; therefore the underlying energy landscapes must possess a kind of benign structure. If evolution can navigate these landscapes, then, with enough data and compute, machine learning should recover the mapping from amino-acid sequence to three-dimensional structure.
This account has rhetorical and inductive appeal. It treats evolution as evidence about the computational nature of protein folding and interprets AlphaFold as a natural consequence of biological priors. But the argument, as usually presented, fails to acknowledge what would be required for it to count as a formal heuristic. It presumes that evolutionary success necessitates the existence of a simple, learnable mapping. It presumes that the folding landscape is sufficiently smooth that the space of biologically relevant proteins is intrinsically easy. And it presumes that the success of a massive deep-learning model confirms that the problem was always secretly tractable.
These presumptions rely on an unspoken quantifier: for all proteins relevant to life, folding is easy. But this “for all” is not legitimate in a complexity-theoretic context unless the instance class has a precise and bounded description. Yudkowsky instead appeals to whatever evolution happened to discover. Evolution’s search process, however, is not a polytime algorithm but an unbounded historical trajectory with astronomical parallelism, billions of years of runtime, and immense filtering by selection pressures. Without explicit bounds, “evolution succeeded” does not imply anything about the inherent computational character of the underlying mapping. It merely establishes that a particular contingent subset of sequences—those the biosphere retained—happened to be foldable by natural dynamics.
If we shift to formal models, the general protein-folding problem remains NP-hard under standard abstraction schemes. That does not mean biological folding is NP-hard, only that no claim about the general tractability of the sequence to structure mapping can be inferred from evolutionary success. What matters for tractability is not the full space of possible proteins but the restricted subset that life explores. Yudkowsky’s argument, by treating evolutionary selection as direct evidence of easy energy landscapes, smuggles in the structural properties of that restricted set without acknowledging that these properties are exactly what must be demonstrated—not simply asserted.
The right computational picture looks very different. The biosphere does not sample uniformly from all possible sequences. Instead, it occupies a tiny, closed, highly structured subset of sequence space—an extraordinarily low-Kolmogorov-complexity region characterized by a few thousand fold families, extensive modularity, and strong physical constraints on designability. This subset bears almost no resemblance to the adversarial or worst-case instances that drive NP-hardness proofs.
Once attention is confined to that biologically realized region, the folding map ceases to be the general NP-hard problem and becomes a promise problem over a heavily compressed instance class. The problem is not hard, it's just big.
Seen this way, the achievement of AlphaFold is not evidence that “protein folding was always solvable,” but evidence that modern machine learning can use enormous non-uniform information—training data, evolutionary alignments, known structures—to approximate a mapping defined over a small and highly regularized domain. The training process acts as a vast preprocessing step, analogous to non-uniform advice in complexity theory. The final trained model is essentially a polytime function augmented by a massive advice string (its learned parameters), specialized to a single distribution. Evolution itself plays a similar role: after billions of years of search, it has curated only those sequences that belong to a region of the landscape where folding is stable, kinetically accessible, and robust to perturbation. The process is not evidence that folding is uniformly simple; it is evidence that evolution found a tractable island inside an intractable ocean.
This distinction matters because it reframes the “predictability” of AlphaFold’s success. Yudkowsky presents folding as solvable because biological energy landscapes are smooth enough to make evolution effective. But smoothness on the evolutionary subset does not entail smoothness on the entire space; nor does it imply that this subset is algorithmically accessible without vast volumes of preprocessing. A complexity-theoretic interpretation views the success of deep learning not as the discovery of a simple universal rule but as the extraction of structure from a domain that has already been heavily pruned, compressed, and optimized by natural history. The learning system inherits its tractability from the fact that the problem has been pre-worked into a low-entropy form.
There is therefore a straightforward computational reason why the “evolution shows folding is easy” argument does not succeed as an explanation: it conflates a historical process without resource bounds with an algorithmic claim that requires them. It interprets the existence of foldable proteins as proof of benign complexity rather than as the output of a long, unbounded filtration that carved out a tractable subclass. The right explanatory frame is not “energy landscapes are nice,” but “biology inhabits a closed problem class with small descriptive complexity, and our algorithms exploit vast non-uniform information about that class.”
Yudkowsky’s argument gestures toward the right conclusion—that solvability was unsurprising—but gives the wrong reason. The crucial structure lies not in universal physics but in the finite, closed domain evolution left to us, and in the immense preprocessing our models perform before they ever encounter a new sequence. The success of AlphaFold was predictable only conditional on the recognition that the real problem is not worst-case folding but folding within a compact distribution carved out by evolutionary history and indexed in publicly available data. What makes the achievement unsurprising is not that physical energy landscapes are globally smooth, but that the domain evolution generated is sufficiently structured, and sufficiently well-sampled, to permit high-fidelity interpolation.
In essence, no one has solved the actual problem, because any solver specialized to the evolutionary subset is guaranteed to fail once the promise is removed; outside that tightly curated domain, the mapping reverts to an unbounded and intractable instance class.
(Context: much contemporary discourse treats machine learning as if it were solving an analytic problem over a vast, effectively unbounded function space—an optimization in a continuous domain, governed by gradient dynamics and statistical generalization. But what learning systems actually deliver, when examined through a computational or logical lens, is a highly non-uniform procedure specialized to a sharply delimited region of instance space. Mixing the analytic metaphor “learning a function over a vast continuous space” with conclusions that require logical quantification “the problem is easy for all relevant inputs” invites people to mistake interpolation on a compact manifold for global tractability. But computation is always local: effective behavior emerges once the space is sufficiently structured, compressed, or bounded by a promise. The solution: Constructive Logic, statements should be made relative to well-defined objects, not idealized totalities.)