• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Верещагин Н. К., Мучник А. А.

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

Кроме того, мы доказываем аналогичные утверждения и для классической шенноновской энтропии.
Мы приводим два различных доказательства обоих результатов --- ``эффективное'' и ``квази-эффективное''. В заключение мы приводим квази-эффективное доказательство усиленного варианта известного результата о существовании слов с невыделяемой общей информацией.  Ранее было известно только неэффективное доказательство этого утверждения.
 
Предварительная публикация результатов данной статьи, относящихся к колмогоровской сложности, появилась в сборнике докладов конференции Сonference on Сomputational Сomplexity в 2001 году. [A. Muchnik and N. Vereshchagin.
``Logical operations and Kolmogorov complexity. II''. Proc. of 16th Annual IEEE Conference on Computational Complexity,
Chicago, June 2001, pp. 256--265.]