В 1999 году Ан. Мучник доказал следующую теорему: для любых
двоичных слов A и B найдётся такое слово X длины примерно K(A|B),
что K(X|A) и K(A|B,X) примерно равны нулю. В доказательстве
использовалось специальное семейство хеш-функций, существование которого
устанавливалось вероятностным методом. Оказывается, вместо этого семейства
можно взять экстрактор с подходящими параметрами и, таким образом,
использовать существующие конструкции экстракторов. В докладе будет
изложено доказательство исходной теоремы при помощи экстракторов и её
вариант для сложности с ограничением на память. Предварительных знаний из
теории экстракторов не требуется.