Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
On The Intrinsic Complexity Of Learning Recursive Functions, Sanjay Jain, Efim Kinber, Christophe Papazian, Carl Smith, Rolf Wiehagen
On The Intrinsic Complexity Of Learning Recursive Functions, Sanjay Jain, Efim Kinber, Christophe Papazian, Carl Smith, Rolf Wiehagen
School of Computer Science & Engineering Faculty Publications
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 iff 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 can behave “orthogonally”.