О совместной условной сложности (энтропии)

Колмогоровская сложность слова $b$ при известном $a$ определяется как минимальная длина программы, перерабатывающей $a$ в $b$. Мы обобщаем это понятие на четверки слов $a,b,c,d$: их совместной условной сложностью $K((a\to c)\land(b\to d))$ называется минимальная длина программы, перерабатывающей $a$ в $c$, а $b$ в $d$. В работе доказано, что совместная условная сложность не выражается через обычные условные и безусловные сложности. Вопрос о существовании задачи о переработке информации, сложность которой не выражается через обычные условные и безусловные сложности, был поставлен А. Шенем на одном из заседаний Колмогоровского семинара в МГУ в 1994 г. Наш результат дает положительный ответ на этот вопрос. Кроме того, мы доказываем аналогичные утверждения и для классической шенноновской энтропии. Мы приводим два различных доказательства обоих результатов – “эффективное” и “квазиэффективное”. В заключение мы приводим квазиэффективное доказательство усиленного варианта известного результата о существовании слов с невыделяемой общей информацией. Ранее было известно только неэффективное доказательство этого утверждения.