A new view of learning is presented. The basis of this view is a natur
al notion of reduction. We prove completeness and relative difficulty
results. An infinite hierarchy of intrinsically more and more difficul
t to learn concepts is presented. Our results indicate that the comple
xity notion captured by our new notion of reduction differs dramatical
ly from the traditional studies of the complexity of the algorithms pe
rforming learning tasks. (C) 1995 Academic Press, Inc.