In [Kan98] learning functions based on these discovery procedures were studied, and it was shown that some of the classes associated with these functions can be identified in the limit (i.e. are learnable) from strings, by a computable function. The time complexity of these functions however was still left an open question.

In this paper we will show that the learning functions for these learnable classes are all NP-hard.