Abstract:
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.