Non-reducible descriptions for conditional Kolmogorov complexity

摘要

Assume that a program p on input a outputs b. We are looking for a shorter program q having the same property (q (a) = b). In addition, we want q to be simple conditional to p (this means that the conditional Kolmogorov complexity K (q I p) is negligible). In the present paper, we prove that sometimes there is no such program q, even in the case when the complexity of p is much bigger than K(b vertical bar a). We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively. (c) 2007 Elsevier B.V. All rights reserved.