Intrinsic complexity of partial learning (Q2419119)

The authors define intrinsic complexity of partial learning, based on reducibilities between learning problems. They observe a rich structure of incomplete degrees, reflecting different types of learning strategies, in terms of topological structures of the target language classes. They also present some examples of complete classes that illuminate the character of the strategies for partial learning of the hardest classes.