Intrinsic Complexity of Uniform Learning Author: Sandra Zilles. Source: Lecture Notes in Artificial Intelligence Vol. 2842, 2003, 39 - 53. Abstract. Inductive inference is concerned with algorithmic learning of recursive functions. In the model of learning in the limit a learner successful for a class of recursive functions must eventually find a program for any function in the class from a gradually growing sequence of its values. This approach is generalized in uniform learning, where the problem of synthesizing a successful learner for a class of functions from a description of this class is considered. A common reduction-based approach for comparing the complexity of learning problems in inductive inference is intrinsic complexity. In this context, reducibility between two classes is expressed via recursive operators transforming target functions in one direction and sequences of corresponding hypotheses in the other direction. The present paper is the first one concerned with intrinsic complexity of uniform learning. The relevant notions are adapted and illustrated by several examples. Characterizations of complete classes finally allow for various insightful conclusions. The connection to intrinsic complexity of non-uniform learning is revealed within several analogies concerning firstly the role and structure of complete classes and secondly the general interpretation of the notion of intrinsic complexity. ©Copyright 2003 Springer