Аннотация:
Колмогоровская сложность слова b при известном a определяется как минимальная длина программы, перерабатывающей a в b. Мы обобщаем это понятие на четверки слов a,b,c,d: их совместной условной сложностью K((a→c)∧(b→d)) называется минимальная длина программы, перерабатывающей a в c, а b в d. В работе доказано, что совместная условная сложность не выражается через обычные условные и безусловные сложности. Вопрос о существовании задачи о переработке информации, сложность которой не выражается через обычные условные и безусловные сложности, был поставлен А. Шенем на одном из заседаний Колмогоровского семинара в МГУ в 1994 г. Наш результат дает положительный ответ на этот вопрос. Кроме того, мы доказываем аналогичные утверждения и для классической шенноновской энтропии. Мы приводим два различных доказательства обоих результатов – “эффективное” и “квазиэффективное”. В заключение мы приводим квазиэффективное доказательство усиленного варианта известного результата о существовании слов с невыделяемой общей информацией. Ранее было известно только неэффективное доказательство этого утверждения.
Образец цитирования:
Н. К. Верещагин, Ан. А. Мучник, “О совместной условной сложности (энтропии)”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Труды МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 103–118; Proc. Steklov Inst. Math., 274 (2011), 90–104
\RBibitem{VerMuc11}
\by Н.~К.~Верещагин, Ан.~А.~Мучник
\paper О совместной условной сложности (энтропии)
\inbook Алгоритмические вопросы алгебры и логики
\bookinfo Сборник статей. К~80-летию со дня рождения академика Сергея Ивановича Адяна
\serial Труды МИАН
\yr 2011
\vol 274
\pages 103--118
\publ МАИК «Наука/Интерпериодика»
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm3316}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2962936}
\elib{https://elibrary.ru/item.asp?id=16766474}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 90--104
\crossref{https://doi.org/10.1134/S008154381106006X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000295983200005}
\elib{https://elibrary.ru/item.asp?id=23965217}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84912009353}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tm3316
https://www.mathnet.ru/rus/tm/v274/p103
Эта публикация цитируется в следующих 4 статьяx:
Nikolay Vereshchagin, “Information disclosure in the framework of Kolmogorov complexity”, Theoretical Computer Science, 940 (2023), 108
Lukas L., Plevny M., “Using entropy for quantitative measurement of operational complexity of supplier-customer system: case studies”, Cent. Europ. J. Oper. Res., 24:2, SI (2016), 371–387
Lukas L., Hofman J., “Operational Complexity of Supplier-Customer Systems Measured by Entropy-Case Studies”, Entropy, 18:4 (2016), UNSP 137
Ewert W., Dembski W.A., Marks Ii R.J., “Measuring Meaningful Information in Images: Algorithmic Specified Complexity”, IET Comput. Vis., 9:6 (2015), 884–894
Цитирование в формате AMSBIB
Обратная связь: