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.
There are plenty of expansions you could make to the "evolutionary subset" (some of them trivial, some of them probably interesting) for which no theorem from complexity theory guarantees that the problem of predicting how any particular instance in the superset folds is intractable.
In general, hardness results from complexity theory say very little about the practical limits on problem-solving ability for AI (or humans, or evolution) in the real world, precisely because the "standard abstraction schemes" do not fully capture interesting aspects of the real-world problem domain, and because the results are mainly about classes and limiting behavior rather than any particular instance we care about.
In many hardness and impossibility results, "adversarial / worst-case" are doing nearly all of the work in the proof, but if you're just trying to build some nanobots you don't care about that. Or more prosaically, if you want to steal some cryptocurrency, in real life you use a side-channel or 0-day in the implementation (or a wrench attack); you don't bother trying to factor large numbers.
IMO it is correct to mostly ignore these kinds of things when building your intuition about what a superintelligence is likely or not likely to be able to do, once you understand what the theorems actually say. NP-hardness says, precisely, that "if a problem is NP-hard (and ), that implies that there is no deterministic algorithm anyone (even a superintelligence) can run, which accepts arbitrary instances of the problem and finds a solution in time steps polynomial in the size of the problem instance.". This statement is precise and formal, but unfortunately it doesn't mention protein folding, and even the implications that it has for an idealized formal model of protein folding are of limited use when trying to predict what specific proteins AlphaFold-N will / won't be able to predict correctly.
Let's look at the most interesting of your arguments first:
"There are plenty of expansions you could make to the "evolutionary subset" (some of them trivial, some of them probably interesting) for which no theorem from complexity theory guarantees that the problem of predicting how any particular instance in the superset folds is intractable."
This response treats the argument as if it were an appeal to worst-case complexity theory—i.e., “protein folding is NP-hard, therefore superintelligence can’t solve it outside the evolutionary subset.” My point rests on entropy and domain restriction, not on NP-hardness per se. It was just convinient to frame it in these terms. And so the existence of trivial or nontrivial supersets where hardness theorems don’t apply is irrelevant. But even so: What goes in a computer is already framed in an abstraction sufficient to determine NP-ness.
In an weird way way, you are actually agreeing with what was written.
My argument is not: “the moment we enlarge the domain, NP-hardness dooms us.”
My argument is: “the moment we enlarge the domain, the entropy of the instance class can increase without bound, and the learned model’s non-uniform ‘advice string’ (its parameters) no longer encodes the necessary constraints.”
One point is demonstrably meh:
In general, hardness results from complexity theory say very little about the practical limits on problem-solving ability for AI (or humans, or evolution) in the real world, precisely because the "standard abstraction schemes" do not fully capture interesting aspects of the real-world problem domain, and because the results are mainly about classes and limiting behavior rather than any particular instance we care about.
Cmputational hardness does retain some relevance for AI, since AI systems exhibit the same broad pattern of struggling with problems whose structure reflects NP-type combinatorial explosion. Verifying a candidate solution can be easy, while discovering can be difficult, impressing your crush “NP-like”: it is straightforward to determine whether a remark is effective, but difficult to determine in advance what remark will succeed, with or without AI.
Now again, I am not discussing complexity, this is more like a predicate argument for why something is a non sequitur.
I am not a "native writer", (originally German, Hungarian) so naturally, I get assistance with grammar but not with formal content. You can already extrapolate the latter fact by my (hand drawn) TSP illustration on the iPad so this question is a bit annoying.
1Fair enough. I found it unreadable in a way I associate with AI (lots of dense words, but tricky to extract the content out of them), and the em dashes are somewhat of a giveaway.
Given how much slop there is I do appreciate if people clarify what they used AI for because I don't want to wade through a ton of slop which wasn't even human written.
Thanks for replying.
1Sure, thank you for thanking.
I will add a few observations/ideas on the topic.
1. It is often claimed that large language models overuse em dashes, but the matter is more nuanced (read an article explicitly on this topic) . Effective prose can employ em dashes for expressivity, and the choice is ultimately stylistic. I, for example, make frequent use of both em and en dashes and have come to prefer them in certain contexts.
2. There is a core epistemic concern: when we detect LLM-like features, we infer “this is produced by an LLM,” yet it does not follow inductively that every text exhibiting similar features must originate from one. Moreover, there is a form of survivorship bias in the texts we fail to identify as machine-generated. Additional complications arise when attempting to delineate where “slop” begins. Does it include grammar correction, stylistic adjustment, paraphrasing, revision, or prompt-driven rewriting?
3. The emphasis should rest primarily on content rather than on presentation. The central question is logical: could an LLM generate this material at scale? For instance, external references—such as video links, illustrations, or other artifacts—may alter that assessment.
For the content above, it stands on its own ground as a formal argument: Entropy (both energetic and algorithmic) behaves, in computational reasoning, exactly like a classical logical fixed point—capable of certifying a stabilized structure but never capable of generating or justifying that structure. Latter is always outside the system. It's a bit related to Löb's Theorem, which many people take as a strengthening, some as a logic fixed point. Whatever it is, classic theory of computation (1930-1970) is overlooked in 2025,
I want to see the post without AI-assisted editing. In the conversation with an AI from which the post's output came, I'd rather have seen the prompts, not the output. Give me the low-effort input, give me the typos and grammar errors. Most posts have flaws; it makes it easier for people to find many of them if you don't have an AI put a layer of paint over your writing. For a good effort post, it's in my opinion important to be able to find what flaws remain. I am not at all saying this is a bad post, just that I don't like having to read it secondhand; I definitely appreciate AI's thoughts on it, but AI can only speak for itself, not for you.
1
1
1This sounds like you are giving advice for someone that is rather interested in writing posts, not developing formal arguments... In logic we are searching for transitivity and rigor, not some modulo aesthetic preference, perhaps you overlooked that the content above is "somewhat" independent of its prosaic form.
"Most posts have flaws"
Where to find flaws in the argument presented... There could be several places where my reasoning can be challenged, the key is to do so without endorsing Yudkowsky’s views.
The game is a bit unfair, as it inherently easier to "destroy" positivistic arguments with first order inference: entropy, smoothness etc. is basically where all limitative theorems reside, arguments relying on these often collapse under scrutiny, most of the time the failure is baked into the system.
The whole "less wrong shtick" forgets that sometimes there is only "wrong". As if it were so simple to convert smartness into casino winnings... Different people would be rich.
Note: I will slowly start to delete posts like this due to irrelevancy and redundancy.
(not enhanced)
"Editing with" AI does not consistently preserve semantics, or I wouldn't ask. Incidentally, lesswrong has a human editor available, just ask in the intercom bubble.
There are many places where I'm confused, and suspect semantics were not preserved, and it would be much more efficient to show me the prompts than for me to nitpick all the little points. The post seems to overall make an interesting point. I am not telling you it's a bad post. May I see the prompts?
On semantics:
Actually semantics "can" be conserved, an example.
- Change in semantics: "This is my second car" vs "this is my second skateboard".
- Change in syntactics: "This is my second car" vs "this is my third car".
- No formal change in the strict sense: "This is my second car" vs "This is—actually—my second car!"
Change during prompting: "Can be both, either, neither."
Considering the prompting itself:
I copy/pasted a rough drafts (2-4 paragraphs?) and wrote something like: "Improve." And then I edited again.
On the opaqueness:
The problem could be "limitative" thinking. Most of weak logics is, eliminative (e.g. implication A -> B is elimination of A etc.). We can only look for contradictions and check for soundness.
On the post:
We can reduce it to a premise:
- "Every physically lawful protein has a well-defined ground-state structure determined by a finite reduction." ≈ "Given unbounded time/energy, we can in principle compute the fold of any amino-acid sequence."
and show, that from:
- "Biological evolution, using only local variation and selection, has discovered many stable, functional proteins."
...it does NOT follow that:
- "Therefore the space of evolution-accessible proteins has simple, exploitable structure, (shallow energy landscapes) so we should expect to be able to build a practical ML system that reliably predicts their structures (or designs new ones) given enough data and compute."
More context:
- Under a finite reduction (a model of folding with well-ordering property on a given lattice), protein folding is expressive enough to simulate arbitrary computation: Hence, the general folding problem is Turing-complete.
So: Every computable function must impose a final blur over that discrete lattice: a smoothing, regularization, or bounded-precision step that ensures computability. Without this blur, the system would risk confronting an unsolvable folding instance that would take forever. Excluding such cases implicitly constitutes a decision about an undecidable set. (Interestingly the 'blur' itself has also a 'blur', call it sigmoid, division etc.)
We can never determine exactly what potential structure is lost in this process, which regions of the formal folding landscape are suppressed or merged by the regularization that keeps the model finite and tractable, unless we train a better model that is sharper, but the problem repeats.
And yes, that means: We don't know if ML will produce diamond bacteria. Could be, could be not.
On Bayesianism:
Since it is popular here, the failure could be explained as: No Bayesian system can coherently answer the meta-question:
- “What is the probability that I can correctly assign probabilities?”
An analogy: Consider the task of factoring every number between 1 and finite n using resources limited by some parameter m. We know in the abstract that factoring is computable, and we have strong reasons to believe that a polynomial-time algorithm exists. Yet none of this tells us whether such an algorithm can be carried out within the bound m. The existence of a procedure in principle does not reveal the resource profile of any procedure in practice. Even if the number system over [1,n] has clean analytic regularities—predictable prime density, well-behaved smoothness properties, low descriptive complexity—these features offer no constructive bridge from “a factoring algorithm must exist” to “a factoring algorithm exists under this specific resource limit.” The arithmetic regularities describe the domain; they do not generate the algorithm or its bounds.
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 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. With a bit hand-waving,[1]
Bn≪Σn,KC(Bn)≪KC(Σn),Struct(Bn)⋐Structadv,F|Bn∈P/polybutF∉P/poly.
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 “classic” 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. The argument above says: computation is always local, effective behavior emerges once the space is sufficiently structured, compressed, or bounded by a promise. It follows from “constructive logic,” computational statements should be made relative to well-defined objects, not idealized totalities.)
Bn, biologically realized sequences of length (n); Σn, sequences
KC(⋅) Kolmogorov complexity; Struct(Bn), reductions realized by Bn; adv, adversarial or worst-case structures; F|Bn, folding restricted to biological instances; P/poly, non-uniform polynomial time.