The Complexity of Transforming Problem Instances