Non-reducible descriptions for conditional Kolmogorov complexity |
| |
Authors: | Andrej Muchnik Alexander Shen Mikhail Ustinov Nikolai Vereshchagin Michael Vyugin |
| |
Affiliation: | 1. Institute of New Technologies, Russian Federation;2. LIF CNRS, CMI, 39 rue Joliot-Curie, 13453 Marseille, Cedex 13, France;3. Moscow State University, Russian Federation |
| |
Abstract: | 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|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|a). We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|