ON THE INTRINSIC COMPLEXITY OF LEARNING

Authors
FREIVALDS R KINBER E SMITH CH
Citation
R. Freivalds et al., ON THE INTRINSIC COMPLEXITY OF LEARNING, Information and computation, 123(1), 1995, pp. 64-71
Citations number
21
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
123
Issue
1
Year of publication
1995
Pages
64 - 71
Database
ISI
SICI code
0890-5401(1995)123:1<64:OTICOL>2.0.ZU;2-Z
Abstract
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.