Kolmogorov complexity
The conditional Kolmogorov complexity of two strings formula_3 is, roughly speaking, defined as the Kolmogorov complexity of "x" given "y" as an auxiliary input to the procedure.