The ability to re-represent information---i.e., to see things in new ways---is essential for human reasoning, creativity, and learning. It forms the foundation of insight problem solving and scientific explanation, and is hypothesized to play a pivotal role in concept development in children. Re-representation is useful because it allows a cognizer to make sense of things in ways that were previously impossible. Yet, invoking this operation can quickly become computationally intractable in light of the combinatorial explosion of re-representation options to consider. Although this intractability may explain why discovering useful ways of re-representing information can be cognitively challenging at times (as in insight puzzles and creativity), it seems difficult to reconcile with automatic and apparently effortless forms of re-representation (as in everyday analogizing and children's development of concepts). To get more insight into the conditions that can make re-representation tractable, we performed computational complexity analyses of a formal model of re-representation as invoked in analogy derivation. We will discuss how our complexity results can help explain when and why re-representation can be invoked effectively and efficiently.