computability
What can be learned at all?
It is 1984, and 'learning from examples' is still a fuzzy intuition rather than a mathematical object. Make it precise: define exactly what it means for a concept to be learnable from data — how much data, how much computation, what guarantee — and then exhibit a concept class that is provably NOT learnable in polynomial time, showing the field has hard limits and not just unsolved engineering. A rigorous definition is the whole contribution; without it, claims about what machines can learn are untestable. Get it wrong and the field either overpromises, treating every learning task as merely a matter of more compute, or gives up on tasks that are in fact tractable — a theory of the learnable is what separates engineering from wishful thinking.
Who this problem belongs to
The two figures whose methods fit it best, out of 46 in contention.
This problem is a description of Valiant's actual 1984 contribution. 'A Theory of the Learnable' (CACM, 1984) defined PAC learning: a learner draws polynomially many examples from an unknown distribution and must, with high probability, output a hypothesis of low error in polynomial time. Every phrase in the prompt — how much data, how much computation, what guarantee — names a parameter of his definition. He also delivered the hardness half, arguing (under standard complexity assumptions) that natural classes like general Boolean formulae resist efficient learning, a line sharpened with Kearns and by Pitt into representation-dependent NP-hardness results. His earlier complexity work, including #P-completeness of the permanent (1979), supplied exactly the resource-bounded framing the definition needed. One caveat: the tight sample-complexity characterization via VC dimension came from Blumer, Ehrenfeucht, Haussler, and Warmuth in 1989.
Working with Chervonenkis in Moscow, Vapnik had built the statistical half of this answer more than a decade before 1984: their 1968-71 uniform-convergence theorems show empirical risk minimization generalizes exactly when the class's VC dimension is finite, with explicit finite-sample, distribution-free bounds — precisely the 'how much data, what guarantee' machinery the problem demands. Blumer, Ehrenfeucht, Haussler, and Warmuth later proved that VC dimension characterizes PAC sample complexity, fusing his framework with Valiant's. What his toolkit lacks is the computational half: VC theory is silent on polynomial time, and exhibiting a class that is information-theoretically learnable yet computationally intractable requires complexity-theoretic or cryptographic assumptions outside his apparatus. He owns the definition-of-learnability axis and cedes the hardness exhibit to the complexity theorists — the second-strongest claim in this room.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
46 figures are scored on this problem. Draw it in a battle to see where you land.