Short lists with short programs in short time

Computational Complexity. 2018. Vol. 27. No. 1. P. 31–61.

Верещагин Н. К., Баувенс Б. Ф., Makhlin A., Zimand M.

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 polynomial size guaranteed to contain a $O(\log |x|)$-short program for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal because we prove that such a list must have size $\Omega(|x|^2)$. Finally we show that for some machines, computable lists containing a shortest program must have length $\Omega(2^{|x|})$.

Ключевые слова: Kolmogorov complexity, on-line matching, expander graph, list approximator

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Теоретическая информатика (2018)