Upper Semi-Lattice of Binary Strings with the Relation ``$x$ is simple conditional to $y$'' Andrei Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshagin Abstract: Upper semi­lattice of binary strings with the relation ``x is simple conditional to y'' Andrei Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshagin We study the properties of the set of binary strings with the relation ``the Kolmogorov complexity of x conditional to y is small''. We prove that there are pairs of strings which have no greatest common lower bound with respect to this pre­order. We present several examples when the greatest common lower bound exists but its complexity is much less than mutual information (extending G'acs and K¨orner result).