Complexity-theory proof of ML impossibility collapses under scrutiny

A 2024 paper in Computational Brain & Behavior by van Rooij, Guest, de Haan, Adolfi, Kolokolova, and Rich claimed to prove that achieving human-level performance through machine learning is computationally impossible. The proof, dubbed the "Ingenia Theorem," attempted to reduce a known NP-hard problem to the task of learning a human-level classifier from data. The result circulated widely in machine learning circles as a potential hard limit on AI capabilities.

A rebuttal published this week in the same journal dismantles the proof with a simple observation: the original authors never mathematically defined "human-level classifier." They introduced a construct corresponding to "distribution of human situation-behaviour tuples" when framing the problem, then quietly swapped it for "all polytime-sampleable distributions" in the formal proof. That substitution invalidates the entire argument. Under the same logic, the proof would also declare learning to classify ImageNet intractable—a claim falsified by years of production models.

Mike Guerzhoy, the rebuttal's author, traces a historical pattern: Penrose's arguments about consciousness, Chomsky's claims about language learning, and now the Ingenia Theorem all follow the same structure. Each introduces an informal intuition ("human-level," "understanding," "grammar") then replaces it with a formal construct that no longer matches the original claim. The sleight-of-hand is subtle enough to survive peer review but collapses under close reading.

The episode exposes how difficult it remains to formalize "human-level" in a way that survives contact with actual learning systems. Whether complexity theory can ever place meaningful bounds on AI capabilities—or whether those bounds will always dissolve under scrutiny of their definitions—remains open. The next attempt will need to define its terms before it starts the proof.