Short lists with short programs in short time - a short proof

2013/02/05 by Marius Zimand, Zimand, Marius
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1302.1109

arxiv created 2013/02/05 · openalex publication_date 2013/02/05 · arxiv updated 2013/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Short lists for shortest descriptions in short time

Related

• Short lists with short programs in short time
• Short lists for shortest descriptions in short time
• Linear list-approximation for short programs (or the power of a few random bits)
• Short lists with short programs for functions
• On the Running Time of the Shortest Programs