Barriers to Complexity-Theoretic Proofs that Achieving AGI Using Machine Learning is Intractable
This work addresses foundational issues in AI theory, highlighting incremental challenges in complexity-theoretic arguments about AGI.
The paper critiques a recent proof claiming that achieving human-like intelligence via machine learning is intractable, arguing that the proof relies on an unjustified assumption about data distributions and faces barriers in defining 'human-like' and accounting for inductive biases.
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 identify that the proof relies on an unjustified assumption about the distribution of (input, output) pairs to the system. 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.