Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that sometimes there
is no such program p', even in the case when the complexity
of p is much bigger than K(b|a). We give three different
constructions that use the game approach,
probabilistic arguments and algebraic (combinatorial) arguments,
respectively.