Analogy mapping is an important problem in Cognitive Science. This problem is known to be computationally intractable in general. It has been claimed that the use of schemas (small concept-structures which fully or almost-fully map to larger exemplar concept-structures) can make analogy mapping efficient. In this poster, we give preliminary results of a complexity-theoretic investigation of such claims.