slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Short lists containing short descriptions in short time

Bruno Bauwens
Universite de Lorraine, Nancy
Monday, 7. April 2014 - 10:30
IM, rear building, ground floor
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... more