Many computational models in cognitive science and artificial intelligence face the problem of computational intractability when assumed to operate for unrestricted input domains. Tractability may be achieved by restricting the input domain, but some degree of generality is typically required to model human-like intelligence. Moreover, it is often non-obvious which restrictions will render a model tractable or not. In this talk, we will give an overview of a methodology using mathematical techniques from computational complexity theory that can be used to identify sources of intractability in a model's input domain. We illustrate this methodology by discussing known results for Gentner's Structure-Mapping Theory of analogy derivation as well as the subsidiary processes of analogy-based exemplar retrieval and solution projection invoked in analogical problem solving.