Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-054 | 5th June 2004 00:00

Non-reducible descriptions for conditional Kolmogorov complexity

RSS-Feed

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.



ISSN 1433-8092 | Imprint