Short lists with short programs in short time - a short proof
classification
💻 cs.CC
keywords
shortprooftimearxivbauwensconstructcontainingdescription
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.