Short lists containing short descriptions in short time
Abstract:
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). Generating a short program for a string is a fundamental problem
for example in learning theory.
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. This result has been improved to obtain
lists containing O(1)-short programs by Teutsch and by Zimand.
If we consider computable lists rather than polynomial time computable
lists, we obtain tight bounds for the list sizes:
* There exist computable functions that map every x to a list of size
O(|x|^2) containing a O(1)-short program for x.
* Every computable function generating lists containing c-short programs
for all x, computes infinitely often lists of size at least Omega(|x|^2/c^2).
The quadratic lower bound can be beaten using probabilistic computation:
there exist a randomized algorithm that on input x computes a list of size
|x| that with probability 1-delta contains a O(log |x|/delta)-short
program for x. Moreover, there is a randomized polynomial time algorithm
that on input x computes in polynomial time such a list containing an
Oleft( (log |x|/delta)^2 right)-short program for x. This task is a
rather unexpected example of a task that is not computably solvable but
solvable in probabilistic polynomial time.
Joint work with A. Makhlin, N. Vereshchagin, and M. Zimand
EN
