Van Rooij paper proves human-level AI learning is NP-hard

"The idea that human cognition is, or can be understood as, a form of computation is a useful conceptual tool for cognitive science," opens a paper in Computational Brain & Behavior that then argues the field of AI has quietly conflated that theoretical premise with the practical feasibility of engineering human-level cognition.

Iris van Rooij of Radboud University and five co-authors — Olivia Guest, Federico Adolfi, Ronald de Haan, Antonina Kolokolova and Patricia Rich — publish a mathematical proof they call the Ingenia Theorem, stating that AI-by-Learning is NP-hard. The construction grants a fictional engineer, Dr. Ingenia, idealised conditions: perfect data, access to any present or future ML method, and a low performance threshold. Under those conditions the authors reduce the learning task to the Perfect-vs-Chance decision problem, which Hirahara proved NP-hard in 2022.

The upshot, in the authors' own words: "creating systems with human(-like or -level) cognition is intrinsically computationally intractable," and "any factual AI systems created in the short-run are at best decoys."

They are explicit about the stakes for industry rhetoric. "Claims of 'inevitability' of AGI within the foreseeable future are revealed to be false and misleading," the authors write, framing the dominant paradigm's narrative — that continued scaling will inevitably yield AGI — as resting on an unproved assumption rather than a theorem. Two researchers we track circulated the open-access version through our Who's Who feed, part of a wider revival of attention to the paper a year after its publication.

The constructive half of the paper is not a rejection of computation as a lens on mind. The authors position AI as a theoretical tool for cognitive science — formal models, thought experiments, complexity constraints — rather than an engineering programme aimed at remaking cognition in silicon.