Though much of human problem solving can be accounted for by search in the problem-state space associated with a problem representation, this assumes that the correct problem representation was chosen. In cases where this did not occur, one or more insights may be necessary to alter the problem representation. Within the most formally-stated theory of insight problem solving, the Representation Change Theory of Knoblich et al, various restrictions have been conjectured to make insight problem solving easier. In this poster, we apply computational complexity analysis to test the validity of these conjectures.