Stability of properties of Kolmogorov complexity under relativization
An. A. Muchnik, Andrei Romashchenko · Problems of Information Transmission · 2010
Assume that a tuple of binary strings $$ \bar a $$ = 〈a 1 ..., a n 〉 has negligible mutual information with another string b. Does this mean that properties of the Kolmogorov complexity of $$ \bar a $$ do not change significantly if we relativize them to b? This question becomes very nontrivial when we try to formalize it. In this paper we investigate this problem for a special class of properties (for properties that can be expressed by an ∃-formula). In particular, we show that a random (conditional on $$ \bar a $$ ) oracle b does not help to extract common information from the strings a i .