Let \(\mathbb {B}^*\)  be the set of all finite binary strings and \(\Phi :\mathbb {B}^* \rightarrow \mathbb {B}^*\)  be a computable function. A Kolmogorov complexity \(K_{\Phi }(s)\)  of a binary string \(s\)  with respect to \(\Phi \)  is defined as a minimal length of a string \(s^{\prime }\)  such as \(\Phi (s^{\prime }) = s\) . Since Kolmogorov complexities with respect to any two functions differ only by an additive constant [1]}, it is usually assumed that some canonical function \(\Phi \)  is fixed, and Kolmogorov complexity is denoted simply by \(K(s)\) . Thus, informally \(K(s)\)  could be described as a length of a shortest encoding of the string \(s\) , that allows to completely reconstruct it. Analogously, for two strings \(s,t\in \mathbb {B}^*\) , a conditional Kolmogorov complexity \(K(s|t)\)  is a a length of a shortest encoding of \(s\) , if \(t\)  is known in advance. More information on properties of Kolmogorov complexity can be found in [1]}.
