Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
Pith reviewed 2026-05-23 18:03 UTC · model grok-4.3
The pith
A recent proof that machine learning cannot achieve human-like intelligence depends on an unstated assumption about how input-output pairs are distributed in the data.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The claimed proof that achieving human-like intelligence by learning from data is complexity-theoretically intractable relies on an assumption about the distribution of (input, output) tuples that is not justified by the argument; repairing the proof requires both a precise definition of human-like intelligence and an account of the inductive biases of the concrete machine learning system under consideration, while subset-based repairs face corresponding definitional barriers.
What carries the argument
The unjustified assumption about the distribution of (input, output) tuples in the data, which blocks any complexity bound from applying to actual learning systems.
If this is right
- Any complexity-theoretic claim against ML-based AGI must state and defend its distribution over input-output pairs.
- Definitions of human-like intelligence used in such proofs must be compatible with the inductive biases of the systems they analyze.
- Subset-based variants of the argument require an explicit criterion for which data subsets are admissible.
- General impossibility results cannot treat all possible learners as equivalent.
Where Pith is reading between the lines
- Impossibility arguments may need to be indexed to families of learning algorithms rather than stated in learner-independent terms.
- Empirical measurements of learnability on observed data distributions could provide a practical test independent of the theoretical barriers identified.
Load-bearing premise
That a precise complexity-theoretic definition of human-like intelligence can be stated without also fixing the inductive biases of the particular machine learning system being considered.
What would settle it
A revised proof that derives an intractability result while explicitly stating a data distribution, defining human-like intelligence in a way that does not depend on learner-specific biases, and justifying the choice of data subsets.
read the original abstract
A recent paper (van Rooij et al. 2024) claims to have proved that achieving human-like intelligence using learning from data is intractable in a complexity-theoretic sense. We point out that the proof relies on an unjustified assumption about the distribution of (input, output) tuples in the data. We briefly discuss that assumption in the context of two fundamental barriers to repairing the proof: the need to precisely define ``human-like," and the need to account for the fact that a particular machine learning system will have particular inductive biases that are key to the analysis. Another attempt to repair the proof, by focusing on subsets of the data, faces barriers in terms of defining the subsets.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript argues that the intractability proof in van Rooij et al. (2024) for achieving human-like intelligence via machine learning from data rests on an unstated and unjustified assumption about the distribution of (input, output) tuples. It identifies two primary barriers to repairing the proof—the absence of a precise definition of 'human-like' intelligence and the failure to incorporate the inductive biases of any specific ML system—and notes that an alternative repair strategy based on data subsets encounters similar definitional obstacles.
Significance. If the identification of the distributional assumption is accurate, the paper usefully flags a methodological gap that future complexity-theoretic arguments against ML-based AGI would need to address explicitly. It earns credit for remaining within the scope of a commentary: it neither derives a new proof nor claims to refute the original result, but instead isolates concrete obstacles (precise definitions and inductive biases) that any repair must confront. This framing can help steer subsequent work toward more realistic models of data and learning.
major comments (1)
- [Abstract and barriers discussion] The central claim that van Rooij et al. (2024) relies on an unjustified distributional assumption is stated at a high level in the abstract and the paragraph discussing barriers; without a reconstruction of the relevant step in the original proof (e.g., the precise place where the distribution over tuples is invoked), it is difficult to assess whether the assumption is load-bearing or merely incidental.
minor comments (1)
- The manuscript would benefit from an explicit citation or short quotation locating the distributional assumption inside van Rooij et al. (2024) so readers can verify the critique without consulting the source paper.
Simulated Author's Rebuttal
We thank the referee for the detailed and constructive review. The suggestion to include a reconstruction of the relevant proof step is well-taken and will improve the clarity of the commentary. We address the major comment below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [Abstract and barriers discussion] The central claim that van Rooij et al. (2024) relies on an unjustified distributional assumption is stated at a high level in the abstract and the paragraph discussing barriers; without a reconstruction of the relevant step in the original proof (e.g., the precise place where the distribution over tuples is invoked), it is difficult to assess whether the assumption is load-bearing or merely incidental.
Authors: We agree that a more explicit reconstruction of the step in van Rooij et al. (2024) where the distributional assumption over (input, output) tuples is invoked would help readers evaluate whether the assumption is load-bearing. In the revised manuscript we will add a concise paragraph (or short subsection) that reconstructs the relevant portion of the original argument, citing the specific place where the uniform or arbitrary distribution over tuples is used to establish intractability. This addition will remain within the scope of a commentary and will not introduce new technical results. revision: yes
Circularity Check
No significant circularity detected
full rationale
This is a short critique paper that identifies an assumption in van Rooij et al. 2024 about the distribution of (input, output) tuples and discusses two barriers to repairing their proof. No derivation chain, predictions, fitted parameters, or first-principles results are presented by the paper itself. The argument is logical identification of an external assumption rather than any self-referential reduction, self-citation load-bearing step, or renaming of known results. The paper is self-contained as commentary and contains no internal quantities that reduce to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Logical analysis of assumptions in a proof is sufficient to identify barriers without needing the full formal details of the original proof.
Reference graph
Works this paper leans on
-
[1]
No free lunch theorem: A review
Stavros P Adam, Stamatios-Aggelos N Alexandropoulos, Panos M Pardalos, and Michael N Vrahatis. No free lunch theorem: A review. Approximation and optimization: Algorithms, complexity and applications , pages 57--82, 2019
work page 2019
-
[2]
Scott Aaronson. Crypto , page 93–108. Cambridge University Press, 2013
work page 2013
-
[3]
Climbing towards nlu: On meaning, form, and understanding in the age of data
Emily M Bender and Alexander Koller. Climbing towards nlu: On meaning, form, and understanding in the age of data. In Proceedings of the 58th annual meeting of the association for computational linguistics , pages 5185--5198, 2020
work page 2020
-
[4]
Occam’s razor and bender and koller’s octopus
Michael Guerzhoy. Occam’s razor and bender and koller’s octopus. In Proceedings of the Sixth Workshop on Teaching NLP , pages 128--129, 2024
work page 2024
-
[5]
NP -hardness of learning programs and partial MCSP
Shuichi Hirahara. NP -hardness of learning programs and partial MCSP . In 63rd annual symposium on foundations of computer science ( FOCS ) , pages 968--979. IEEE, 2022
work page 2022
-
[6]
An enquiry concerning the human understanding: And an enquiry concerning the principles of morals
David Hume. An enquiry concerning the human understanding: And an enquiry concerning the principles of morals . Clarendon Press, 1894
-
[7]
Imagenet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems , volume 25. Curran Associates, Inc., 2012
work page 2012
-
[8]
Natural image statistics and neural representation
Eero P Simoncelli and Bruno A Olshausen. Natural image statistics and neural representation. Annual review of neuroscience , 24(1):1193--1216, 2001
work page 2001
-
[9]
Leslie G Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134--1142, 1984
work page 1984
-
[10]
Reclaiming ai as a theoretical tool for cognitive science
Iris Van Rooij, Olivia Guest, Federico Adolfi, Ronald de Haan, Antonina Kolokolova, and Patricia Rich. Reclaiming ai as a theoretical tool for cognitive science. Computational Brain & Behavior , pages 1--21, 2024
work page 2024
-
[11]
Theoretical analysis of the inductive biases in deep convolutional networks
Zihao Wang and Lei Wu. Theoretical analysis of the inductive biases in deep convolutional networks. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems , volume 36, pages 74289--74338. Curran Associates, Inc., 2023
work page 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.