2014 | OriginalPaper | Buchkapitel
Short Lists with Short Programs in Short Time – A Short Proof
verfasst von : Marius Zimand
Erschienen in: Language, Life, Limits
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Bauwens, Mahklin, Vereshchagin and Zimand [1] and Teutsch [6] 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, which also achieves better values for the main parameters.