6533b831fe1ef96bd1298315
RESEARCH PRODUCT
On the intrinsic complexity of learning
Efim KinberCarl SmithRusins Freivaldssubject
Reduction (complexity)HierarchyTheoretical computer scienceBasis (linear algebra)Computer scienceCompleteness (order theory)Recursive functionsRecursive operatorNatural (music)Inductive reasoningdescription
A new view of learning is presented. The basis of this view is a natural notion of reduction. We prove completeness and relative difficulty results. An infinite hierarchy of intrinsically more and more difficult to learn concepts is presented. Our results indicate that the complexity notion captured by our new notion of reduction differs dramatically from the traditional studies of the complexity of the algorithms performing learning tasks.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1995-01-01 |