Short lists with short programs in short time - a short proof
Zimand, Marius
Original · EN
Bauwens, Mahklin, Vereshchagin and Zimand [ECCC TR13-007] and Teutsch [arxiv:1212.6104] have shown that given a string x it is possible to construct in polynomial time a list containing a short description of it. We simplify their technique and present a shorter proof of this result.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.