The normalized algorithmic information distance can not be approximated

Семенов А. Л., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 527 № S С. 7–12

В работе предлагается система определений для основных понятия теории вычислимости, лежащих в основе математики цифрового мира: алгоритм, вычислимость, исчисление, сложность объекта, приближенная к современным представлениям. Рассматриваются иерархии конечного и проблема непротиворечивости. ...

Добавлено: 6 декабря 2025 г.

Kolmogorov’s Last Discovery? (Kolmogorov and Algorithmic Statistics)

Семенов А. Л., Шень А., Верещагин Н. К., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606

Добавлено: 16 января 2025 г.

On information content in certain objects

Верещагин Н. К., / Series arXiv "math". 2024.

Добавлено: 19 августа 2024 г.

Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time

Баувенс Б. Ф., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9

Добавлено: 22 марта 2023 г.

Inequalities for space-bounded Kolmogorov complexity

Баувенс Б. Ф., Gács P., Romashchenko A. и др., Computability 2022 Vol. 11 No. 3-4 P. 165–185

Добавлено: 23 декабря 2022 г.

Information disclosure in the framework of kolmogorov complexity

Верещагин Н. К., Theoretical Computer Science 2023 Vol. 940 P. 108–122

Добавлено: 19 декабря 2022 г.

Predictions and Algorithmic Statistics for Infinite Sequences

Милованов А. С., , in: Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings.: Springer, 2021. Ch. 17 P. 283–295.

Добавлено: 11 августа 2021 г.

Information Distance Revisited

Баувенс Б. Ф., , in: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1–46:14.

Добавлено: 20 марта 2020 г.

Descriptive complexity of computable sequences revisited

Верещагин Н. К., Theoretical Computer Science 2020 Vol. 809 P. 531–537

Добавлено: 17 января 2020 г.

Complexity of Equivalence Relations and Preorders from Computability Theory

Яновский Е. А., Miller R., Ng K. M. и др., Journal of Symbolic Logic 2014 Vol. 3 No. 79 P. 859–881

Добавлено: 25 февраля 2019 г.

On maximal subgroups of the group of recursive permutations

Kolmakov E.A., Marchenkov S. S., Moscow University Computational Mathematics and Cybernetics 2016 Vol. 40 No. 3 P. 128–132

Добавлено: 5 декабря 2018 г.

Algorithmic Statistics: Forty Years Later.

Shen A., Верещагин Н. К., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.

Добавлено: 26 октября 2018 г.

Computability and Complexity

Day A., Fellows M., Greenberg N. и др., Berlin: Springer, 2017.

Добавлено: 26 октября 2018 г.

On Algorithmic Statistics for Space-bounded Algorithms

Милованов А. С., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848

Добавлено: 17 октября 2018 г.

Plain stopping time and conditional complexities revisited

Пособин Г. И., Shen A., Andreev M., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–24.

Добавлено: 11 октября 2018 г.

A Structural Lemma for Deterministic Context-Free Languages

Рубцов А. А., , in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings.: Cham: Springer, 2018. P. 553–565.

Добавлено: 12 сентября 2018 г.

Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms

Милованов А. С., , in: Sailing Routes in the World of Computation.: Springer, 2018. P. 287–296.

Добавлено: 4 сентября 2018 г.

On Algorithmic Statistics for Space-Bounded Algorithms

Милованов А. С., , in: Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017)Vol. 10304.: Luxemburg: Springer, 2017. P. 232–244.

Добавлено: 15 октября 2017 г.

Kolmogorov complexity and algorithmic randomness

Shen A., Uspensky V. A., Верещагин Н. К., American Mathematical Society, 2017.

Добавлено: 12 октября 2017 г.

Stochasticity in Algorithmic Statistics for Polynomial Time

Верещагин Н. К., Милованов А. С., , in: 32nd Computational Complexity Conference.: Вадерн: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1–18.

A fundamental notion in Algorithmic Statisticsis that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical ...

Добавлено: 12 октября 2017 г.

Short lists with short programs in short time

Верещагин Н. К., Баувенс Б. Ф., Makhlin A. и др., Computational Complexity 2018 Vol. 27 No. 1 P. 31–61

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Добавлено: 22 апреля 2017 г.

Stochasticity in Algorithmic Statistics for Polynomial Time

Верещагин Н. К., Милованов А. С., / Series Technical report "Electronic Colloquium on Computational Complexity". 2017. No. TR17-043.

Добавлено: 7 марта 2017 г.