Please use this identifier to cite or link to this item: https://doi.org/10.1016/S0890-5401(03)00059-2
Title: On the intrinsic complexity of learning recursive functions
Authors: Jain, S. 
Kinber, E.
Papazian, C.
Smith, C.
Wiehagen, R.
Issue Date: 2003
Source: Jain, S.,Kinber, E.,Papazian, C.,Smith, C.,Wiehagen, R. (2003). On the intrinsic complexity of learning recursive functions. Information and Computation 184 (1) : 45-70. ScholarBank@NUS Repository. https://doi.org/10.1016/S0890-5401(03)00059-2
Abstract: The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhibited and necessary and sufficient conditions for completeness are derived. Informally, a class is complete if both its topological structure is highly complex while its algorithmic structure is easy. Some self-describing classes turn out to be complete. Furthermore, the structure of the intrinsic complexity is shown to be much richer than the structure of the mind change complexity, though in general, intrinsic complexity and mind change complexity can behave "orthogonally".
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/39188
ISSN: 08905401
DOI: 10.1016/S0890-5401(03)00059-2
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

6
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

6
checked on Nov 4, 2017

Page view(s)

47
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.