  In this paper we study the complexity of solving a problem when a solution of
a similar instance is known. This problem is relevant whenever instances may
change from time to time, and known solutions may not remain valid after the
change. We consider two scenarios: in the first one, what is known is only a
solution of the problem before the change; in the second case, we assume that
some additional information, found during the search for this solution, is also
known. In the first setting, the techniques from the theory of NP-completeness
suffice to show complexity results. In the second case, negative results can
only be proved using the techniques of compilability, and are often related to
the size of considered changes.
