• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Short lists with short programs in short time

Computational Complexity. 2018. Vol. 27. No. 1. P. 31-61.
Vereshchagin N., Bauwens B. F., 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|})$.