On the computational challenges of analogy-based generalization

One prominent account of concept and category learning is that concepts and categories (jointly referred to as ‘generalizations’) are abstractions derived by extracting common analogical structure from sets of exemplars. This account enjoys considerable empirical support and has informed the design of models of learning in artificial intelligence. One aspect of the theory that has received little attention to date is the computational tractability of the processes that it postulates. In this paper, we assess the (in)tractability of analogy-based generalization using proof techniques from computational complexity theory. Our results reveal some unique computational challenges for analogy-based generalization, which it seems need to be addressed before the account can claim cognitive plausibility.