Computational Learning Theory

Computational learning theory is the branch of learning theory that studies learning under computational constraints. Where formal learning theory asks which concept classes are learnable in principle, computational learning theory asks which are learnable in polynomial time — and which require resources that grow exponentially with problem size. The field's central framework is PAC (Probably Approximately Correct) learning, introduced by Leslie Valiant in 1984, which demands that a learner produce a hypothesis that is probably approximately correct, using time and sample size polynomial in the relevant parameters.

The computational perspective transforms philosophical questions about induction into complexity-theoretic ones. A concept class may be learnable in the limit yet not PAC-learnable; it may be PAC-learnable only with access to membership queries or only with improper hypotheses. The boundary between tractable and intractable learning mirrors the broader P versus NP boundary, and some of the deepest open questions in the field concern whether natural concept classes — neural network architectures, decision trees, boolean formulas — are efficiently learnable under standard cryptographic assumptions.