  We prove a Kolmogorov complexity variant of the birthday paradox.
Sufficiently sized random subsets of strings are guaranteed to have two members
x and y with low K(x/y). To prove this, we first show that the minimum
conditional Kolmogorov complexity between members of finite sets is very low if
they are not exotic. Exotic sets have high mutual information with the halting
sequence.
