Аннотация:
С точки зрения колмогоровской сложности рассматриваются задачи о построении сообщений, которые содержат разное количество информации о заданном объекте в зависимости от того, какой дополнительной информацией располагает получатель. Предположим, что получатель знает слово a и мы хотим сообщить получателю информацию о некотором слове b, причем таким образом, чтобы наше сообщение само по себе (без a) не позволяло восстановить b. Оказывается, что это возможно (если слова a и b не слишком просты). Далее рассматриваются более сложные родственные вопросы: что будет, если “противник” знает некоторую информацию c? насколько длинным должно быть сообщение? Мы уточняем эти вопросы, указываем условия, при которых сообщение может иметь полиномиальную длину, и показываем, что они существенны.
Образец цитирования:
Ан. А. Мучник, “Колмогоровская сложность и криптография”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Труды МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 210–221; Proc. Steklov Inst. Math., 274 (2011), 193–203
\RBibitem{Muc11}
\by Ан.~А.~Мучник
\paper Колмогоровская сложность и криптография
\inbook Алгоритмические вопросы алгебры и логики
\bookinfo Сборник статей. К~80-летию со дня рождения академика Сергея Ивановича Адяна
\serial Труды МИАН
\yr 2011
\vol 274
\pages 210--221
\publ МАИК «Наука/Интерпериодика»
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm3328}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2962942}
\elib{https://elibrary.ru/item.asp?id=16766483}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 193--203
\crossref{https://doi.org/10.1134/S0081543811060125}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000295983200011}
\elib{https://elibrary.ru/item.asp?id=24724216}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84866044180}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tm3328
https://www.mathnet.ru/rus/tm/v274/p210
Эта публикация цитируется в следующих 5 статьяx:
Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov, 2024 IEEE Information Theory Workshop (ITW), 2024, 181
Giuseppe Ateniese, Long Chen, Danilo Francati, Dimitrios Papadopoulos, Qiang Tang, Lecture Notes in Computer Science, 13941, Public-Key Cryptography – PKC 2023, 2023, 63
Andrei Romashchenko, Alexander Shen, Marius Zimand, “27 Open Problems in Kolmogorov Complexity”, SIGACT News, 52:4 (2021), 31
Souto A., “Time Bounded Incompressible Theorem Reversed”, 2018 9Th International Conference on Intelligent Systems (Is), eds. JardimGoncalves R., Mendonca J., Jotsov V., Marques M., Martins J., Bierwolf R., IEEE, 2018, 443–447
Tom Arbuckle, Lecture Notes in Computer Science, 7425, Convergence and Hybrid Information Technology, 2012, 633
Цитирование в формате AMSBIB
Обратная связь: