Устойчивость колмогоровских свойств при релятивизации

Предположим, что кортеж слов $\bar a=\langle a_1,\dots,a_n\rangle$ имеет пренебрежимо малую взаимную информацию с некоторым словом $b$. Значит ли это, что свойства колмогоровской сложности набора слов $\bar a$ мало меняются при релятивизации относительно $b$? Если аккуратно формализовать поставленный вопрос, то окажется, что получить на него полный ответ очень непросто. В данной статье эта задача изучается для ограниченного класса свойств (для свойств, выразимых на языке $\exists$-формул). В частности, доказывается, что случайный относительно $\bar a$ оракул $b$ не помогает выделять общую информацию из слов $a_i$.