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

Working paper

Short lists with short programs in short time

Electronic Colloquium on Computational Complexity. Technical report. Hasso-Plattner-Institut, 2013. No. TR13-007.
Bauwens B., Makhlin A., Vereshchagin N., 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|})$.